Divisione di grandi numeri

Question

Ho bisogno di un algoritmo di divisione in grado di gestire numeri interi grandi (128 bit). Ho già chiesto come farlo tramite operatori di spostamento dei bit. Tuttavia, la mia attuale implementazione sembra richiedere un approccio migliore

Fondamentalmente, memorizzo i numeri come due long long unsigned int nel formato

A * 2 ^ 64 + B con B < 2 ^ 64.

Questo numero è divisibile per 24 e voglio dividerlo per A / 24.

Il mio approccio attuale è quello di trasformarlo come

A * 2 ^ 64 + B     A             B
--------------  = ---- * 2^64 + ----
      24           24            24

           A               A mod 24                    B         B mod 24
= floor( ---- ) * 2^64 +  ---------- * 2^64 + floor( ---- ) +   ----------
           24               24.0                      24           24.0

Tuttavia, questo è difettoso.

(Nota che floor è mod e che A % 24 è long double. Le divisioni normali sono memorizzate in 11000, gli interi sono memorizzati in <=>.

Poiché <=> è uguale a <=> in binario, il secondo summand non dovrebbe cambiare qualcosa nell'intervallo del quarto summand poiché è spostato di 64 bit a sinistra.

Quindi, se <=> è divisibile per 24 e B non lo è, mostra facilmente che bug poiché restituisce un numero non integrale.

Qual è l'errore nella mia implementazione?

Answer 1

Il modo più semplice a cui riesco a pensare è quello di trattare i numeri a 128 bit come quattro numeri a 32 bit:

A_B_C_D = A*2^96 + B*2^64 + C*2^32 + D

E quindi esegui una divisione lunga per 24:

E = A/24 (with remainder Q)
F = Q_B/24 (with remainder R)
G = R_C/24 (with remainder S)
H = S_D/24 (with remainder T)

Dove X_Y significa X*2^32 + Y. Quindi la risposta è E_F_G_H con il resto T. In qualsiasi momento hai solo bisogno di dividere i numeri a 64 bit, quindi questo dovrebbe essere fattibile solo con operazioni intere.

Answer 2

Potrebbe forse essere risolto con la moltiplicazione inversa? La prima cosa da notare è che 24 == 8 * 3 quindi il risultato di

a / 24 == (a >> 3) / 3

Lascia x = (a >> 3) quindi il risultato della divisione è 8 * (x / 3). Ora resta da trovare il valore di x / 3.

L'aritmetica modulare afferma che esiste un numero n tale che n * 3 == 1 (mod 2^128). Questo dà:

x / 3 = (x * n) / (n * 3) = x * n

Resta da trovare la costante <=>. C'è una spiegazione su come farlo su wikipedia . Dovrai anche implementare funzionalità per moltiplicare i numeri a 128 bit.

Spero che questo aiuti.

/A.B.

Answer 3

Non dovresti usare long double per il tuo " divisioni normali " ma anche numeri interi lì. <=> non ha abbastanza cifre significative per ottenere la risposta giusta (e comunque l'intero punto è farlo con operazioni intere, giusto?).

Answer 4

  

Poiché 24 è uguale a 11000 in binario, il secondo summand non dovrebbe cambiare qualcosa nell'intervallo del quarto summand poiché è spostato di 64 bit a sinistra.

La tua formula è scritta in numeri reali. (Un mod 24) / 24 può avere un numero arbitrario di decimali (1/24 è ad esempio 0,041666666 ...) e può quindi interferire con il quarto termine della decomposizione, anche una volta moltiplicato per 2 ^ 64.

La proprietà che Y * 2 ^ 64 non interferisce con le cifre binarie di peso inferiore in un'aggiunta funziona solo quando Y è un numero intero.

Answer 5

Non farlo.

Vai a prendere una libreria per fare queste cose - sarai incredibilmente grato di aver scelto quando esegui il debug di strani errori.

Snippets.org aveva una libreria BigInt C / C ++ sul suo sito qualche tempo fa, Google ha anche pubblicato quanto segue: http://mattmccutchen.net/bigint/