Come posso aggiungere e sottrarre interi a 128 bit in C o C ++ se il mio compilatore non li supporta?

Sto scrivendo un compressore per un lungo stream di numeri a 128 bit. Vorrei memorizzare i numeri come differenze – memorizzando solo la differenza tra i numeri anziché i numeri stessi perché posso raggruppare le differenze in meno byte perché sono più piccole.

Tuttavia, per la compressione, devo sottrarre questi valori a 128 bit, e per la decompressione devo aggiungere questi valori. La dimensione intera massima per il mio compilatore è larga 64 bit.

Qualcuno ha qualche idea per farlo in modo efficiente?

Se tutto ciò di cui hai bisogno è addizione e sottrazione e hai già i tuoi valori a 128 bit in formato binario, una libreria potrebbe essere utile ma non strettamente necessaria. Questa matematica è banale da fare da solo.

Non so cosa usi il compilatore per i tipi a 64 bit, quindi userò INT64 e UINT64 per quantità di interi a 64 bit con segno e senza segno.

class Int128 { public: ... Int128 operator+(const Int128 & rhs) { Int128 sum; sum.high = high + rhs.high; sum.low = low + rhs.low; // check for overflow of low 64 bits, add carry to high if (sum.low < low) ++sum.high; return sum; } Int128 operator-(const Int128 & rhs) { Int128 difference; difference.high = high - rhs.high; difference.low = low - rhs.low; // check for underflow of low 64 bits, subtract carry to high if (difference.low > low) --difference.high; return difference; } private: INT64 high; UINT64 low; }; 

Dai un’occhiata a GMP .

 #include  #include  int main (int argc, char** argv) { mpz_t x, y, z; char *xs, *ys, *zs; int i; int base[4] = {2, 8, 10, 16}; /* setting the value of x in base 10 */ mpz_init_set_str(x, "100000000000000000000000000000000", 10); /* setting the value of y in base 16 */ mpz_init_set_str(y, "FF", 16); /* just initalizing the result variable */ mpz_init(z); mpz_sub(z, x, y); for (i = 0; i < 4; i++) { xs = mpz_get_str(NULL, base[i], x); ys = mpz_get_str(NULL, base[i], y); zs = mpz_get_str(NULL, base[i], z); /* print all three in base 10 */ printf("x = %s\ny = %s\nz = %s\n\n", xs, ys, zs); free(xs); free(ys); free(zs); } return 0; } 

L'output è

 x = 10011101110001011010110110101000001010110111000010110101100111011111000000100000000000000000000000000000000 y = 11111111 z = 10011101110001011010110110101000001010110111000010110101100111011111000000011111111111111111111111100000001 x = 235613266501267026547370040000000000 y = 377 z = 235613266501267026547370037777777401 x = 100000000000000000000000000000000 y = 255 z = 99999999999999999999999999999745 x = 4ee2d6d415b85acef8100000000 y = ff z = 4ee2d6d415b85acef80ffffff01 

Avendo imbattuto per caso in questo post relativamente vecchio, ho pensato che fosse pertinente elaborare la precedente congettura di Volte a beneficio dei lettori inesperti.

In primo luogo, l’intervallo firmato di un numero a 128 bit è da -2 127 a 2 127 -1 e non da -2 127 a 2 127 come inizialmente stabilito.

In secondo luogo, a causa della natura ciclica dell’aritmetica finita, il più grande differenziale richiesto tra due numeri a 128 bit è da -2 127 a 2 127 -1, che ha un prerequisito di memoria di 128 bit, non 129. Sebbene (2 127 -1) – (-2 127 ) = 2 128 -1 che è chiaramente maggiore del nostro massimo 2 127 -1 numero intero positivo, l’overflow aritmetico garantisce sempre che la distanza più vicina tra due numeri n bit sempre rientri nell’intervallo da 0 a 2 n – 1 e quindi implicitamente da -2 n -1 a 2 n -1 -1.

Per chiarire, esaminiamo innanzitutto come un ipotetico processore a 3 bit implementerebbe l’addizione binaria. Ad esempio, si consideri la seguente tabella che illustra l’intervallo senza segno assoluto di un numero intero a 3 bit.

0 = 000b
1 = 001b
2 = 010b
3 = 011b
4 = 100b
5 = 101b
6 = 110b
7 = 111b —> [Torna a 000b su overflow]

Dalla tabella di cui sopra è facilmente evidente che:

001b (1) + 010b (2) = 011b (3)

È anche evidente che l’aggiunta di uno qualsiasi di questi numeri con il suo complemento numerico produce sempre 2 n -1:

010b (2) + 101b ([complemento di 2] = 5) = 111b (7) = (2 3 -1)

A causa del trabocco ciclico che si verifica quando l’aggiunta di due numeri n- bit risulta in un risultato ( n +1) -bit, ne consegue che l’aggiunta di uno qualsiasi di questi numeri con il suo complemento numerico + 1 produrrà sempre 0:

010b (2) + 110b ([complemento di 2] + 1) = 000b (0)

Quindi possiamo dire che [complemento di n ] + 1 = – n , così che n + [complemento di n ] + 1 = n + (- n ) = 0. Inoltre, se ora sappiamo che n + [complemento di n ] + 1 = 0, quindi n + [complemento di nx ] + 1 deve = n – ( nx ) = x .

Applicando questo alla nostra tabella originale a 3 bit si ottiene:

0 = 000b = [complemento di 0] + 1 = 0
1 = 001b = [complemento di 7] + 1 = -7
2 = 010b = [complemento di 6] + 1 = -6
3 = 011b = [complemento di 5] + 1 = -5
4 = 100b = [complemento di 4] + 1 = -4
5 = 101b = [complemento di 3] + 1 = -3
6 = 110b = [complemento di 2] + 1 = -2
7 = 111b = [complemento di 1] + 1 = -1 —> [Torna a 000b su overflow]

Se l’astrazione rappresentazionale è positiva, negativa o una combinazione di entrambi come implicita con l’aritmetica a due complementi firmata, ora abbiamo 2 pattern n- bit che possono perfettamente servire sia da 0 a 2 n -1 che da 0 a – (2 negativo) n ) -1 intervalli come e quando richiesto. In effetti, tutti i processori moderni impiegano proprio tale sistema per implementare circuiti di ALU comuni sia per le operazioni di addizione che di sottrazione. Quando una CPU incontra un’istruzione di sottrazione i1 - i2 , esegue internamente un’operazione [complemento + 1] su i2 e successivamente elabora gli operandi attraverso il circuito di addizione per calcolare i1 + [complemento di i2 ] + 1. Ad eccezione di un ulteriore flag di overflow di carry / sign XOR, sia l’aggiunta firmata che non firmata, e per sottrazione implicita, sono impliciti.

Se applichiamo la tabella sopra alla sequenza di input [-2 n -1 , 2 n -1 -1, -2 n -1 ] come presentato nella risposta originale di Volte, siamo ora in grado di calcolare i seguenti differenziali n-bit:

diff n.1:
(2 n -1 -1) – (-2 n -1 ) =
3 – (-4) = 3 + 4 =
(-1) = 7 = 111b

diff # 2:
(-2 n -1 ) – (2 n -1 -1) =
(-4) – 3 = (-4) + (5) =
(-7) = 1 = 001b

Iniziando con il nostro seme -2 n -1 , siamo ora in grado di riprodurre la sequenza di input originale applicando in sequenza tutti i suddetti differenziali:

(-2 n -1 ) + (diff # 1) =
(-4) + 7 = 3 =
2 n -1 -1

(2 n -1 -1) + (diff # 2) =
3 + (-7) = (-4) =
-2 n -1

Ovviamente si potrebbe desiderare di adottare un approccio più filosofico a questo problema e di congetturare il motivo per cui 2 n numeri sequenzialmente ciclici richiederebbero più di 2 n differenziali ciclicamente sequenziali?

Taliadon.

Boost 1.53 ora include multiprecision:

 #include  #include  // Requires Boost 1.53 or higher // build: g++ text.cpp int main() { namespace mp = boost::multiprecision; mp::uint128_t a = 4294967296; mp::uint256_t b(0); mp::uint512_t c(0); b = a * a; c = b * b; std::cout << "c: " << c << "\n"; return 0; } 

Produzione:

 ./a.out c: 340282366920938463463374607431768211456 

C’è molta letteratura riguardante la matematica dei numeri interi di grandi dimensioni. Puoi utilizzare una delle librerie liberamente disponibili (vedi link) oppure puoi crearne una tua. Anche se dovrei avvertirti, per qualcosa di più complicato di addizione e sottrazione (e turni), dovrai usare algoritmi non banali.

Per aggiungere e sottrarre, puoi creare una class / struttura che contiene due interi a 64 bit. Puoi usare la semplice matematica scolastica per fare l’addizione e la sottrazione. Fondamentalmente, fai quello che fai con una matita e un foglio da aggiungere o sottrarre, con un’attenta considerazione per portare / prendere in prestito.

Cerca un numero intero grande. Btw le recenti versioni di VC ++, i compilatori IntelC ++ e GCC hanno tipi interi a 128 bit, anche se non sono sicuro che siano facilmente accessibili come si vorrebbe (sono pensati per essere usati con registri sse2 / xmms).

TomsFastMath è un po ‘come GMP (menzionato sopra), ma è di dominio pubblico, ed è stato progettato da zero per essere estremamente veloce (contiene anche ottimizzazioni del codice assembly per x86, x86-64, ARM, SSE2, PPC32 e AVR32) .

Vale anche la pena notare: se l’objective è semplicemente quello di migliorare la compressione di un stream di numeri preelaborandolo, allora il stream preelaborato non deve essere fatto di esattamente delle differenze aritmetiche. Puoi usare XOR ( ^ ) invece di + e - . Il vantaggio è che uno XOR a 128 bit è esattamente lo stesso di due XOR indipendenti sulle parti a 64 bit, quindi è sia semplice che efficiente.