Divisione di grandi numeri

Ho bisogno di un algoritmo di divisione in grado di gestire interi grandi (128 bit). Ho già chiesto come farlo tramite gli operatori di cambio di bit. Tuttavia, la mia attuale implementazione sembra chiedere per un migliore approccioDivisione di grandi numeri

Fondamentalmente, ho memorizzare i numeri come due long long unsigned int s' nel formato

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

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

Il mio approccio attuale è quella 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 è bacato.

(Si noti che piano è A/24 e che mod è A % 24. Le divisioni normali sono memorizzati in long double, gli interi sono memorizzati in long long unsigned int.

Dal 24 è pari a 11000 in binario, il secondo addendo non dovrebbe cambia qualcosa nell'intervallo del quarto summmo poiché è spostato a 64 bit a sinistra

Quindi, se A * 2^64 + B è divisibile per 24, e B non lo è, mostra facilmente che si tratta di bug poiché restituisce alcuni elementi non integrali numero

Qual è l'errore nella mia implementazione?

fonte

2009-11-27 Etan

Qual è stato il problema con l'approccio del cambio di bit? –

sembra essere eccessivo quando si è già in grado di dividere lo – Etan

Il modo più semplice che posso pensare di fare questo è trattare i numeri a 128 bit come quattro 32 bit numeri:

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

e poi fare lungo la divisione 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 è necessaria solo la divisione dei numeri a 64 bit, quindi questo dovrebbe essere possibile solo con le operazioni integer.

fonte

2009-11-27 13:12:09 interjay

Non impedisce al proprio algoritmo di funzionare, ma F, G e H possono essere ciascuno più grande di 2^32. Ho avuto difficoltà a riconciliarlo con il fatto che la notazione di 'E_F_G_H' sembra concatenazione, ma una volta capito, è un algoritmo molto bello. –

In realtà, F, G e H saranno inferiori a 2^32, perché Q, R e S sono tutti meno di 24. Quindi la notazione E_F_G_H * è * concatenazione. – interjay

Giusto! Ho dimenticato la mia divisione matita e carta ... Mi sono ricordato che c'era una parte spiacevole di indovinare, ma in quel momento il divisore ha troppe cifre. Finché il divisore stesso è abbastanza breve da rientrare nell'intervallo per il quale funziona la divisione primitiva (come nel caso qui), non c'è mai alcun bisogno di indovinare quando si applica l'algoritmo di divisione matita e carta. Dispiace per la confusione. –

Non si dovrebbe utilizzare long double per le "divisioni normali" ma anche gli interi. long double non ha abbastanza cifre significative per ottenere la risposta giusta (e comunque l'intero punto è farlo con le operazioni integer, corretto?).

fonte

2009-11-27 12:31:39

di int64, il punto è semplicemente dividere un int di 128 bit per 24, il che si traduce in un fallimento epico al momento. Il doppio lungo ha 64 bit di mantissa, quindi questo non dovrebbe creare problemi. o lo fa? – Etan

Etan avrebbe dovuto collegarsi alla domanda originale di eir. Sembra che l'obiettivo non sia farlo con i numeri interi, ma farlo a tutti. Inoltre, 'long double' può essere piccolo come un doppio a 64 bit, ma può anche essere più grande (ad esempio un double esteso di 10 byte, ma qualsiasi cosa, in realtà ... IEEE 754 è in gran parte parametrico rispetto alle dimensioni dei bit). Pertanto * potrebbe * possibilmente avere la precisione necessaria (non sto dicendo che è una buona idea usare calcoli a virgola mobile per qualcosa di semplice come l'aritmetica di interi a 128 bit). –

Come dividerlo senza il doppio lungo? – Etan

Poiché 24 è uguale a 11000 in binario, il secondo summe non deve cambiare qualcosa nell'intervallo del quarto summar 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 scomposizione, anche se moltiplicato per 2^64.

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

fonte

2009-11-27 12:32:32

Interferisce in decimali poiché non è possibile scriverli esattamente laggiù. In binario, ha un'implementazione limitata dal 1/24 può essere scritta in una quantità finale di cifre. – Etan

@Etan Davvero? Quante cifre ci vuole per rappresentare 1/24 esattamente in binario allora? (Se è una domanda troppo difficile, inizia con il numero di cifre binarie necessario per rappresentare 1/3 esattamente) –

1/24 = binario 0,00001010101010101 ... la sequenza continua all'infinito. – dave4420

No.

Vai a prendere una libreria per fare questa roba - sarai incredibilmente grato quando hai scelto di eseguire il debug di errori strani.

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

fonte

2009-11-27 12:49:04

Devo farlo manualmente poiché si tratta di un problema ICPC ACM. – Etan

Potrebbe essere possibile risolvere questo problema con una moltiplicazione inversa? La prima cosa da notare è che 24 == 8 * 3 così il risultato di

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

Let x = (a >> 3) allora il risultato della divisione è 8 * (x/3). Ora rimane 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 n. C'è una spiegazione su come farlo su wikipedia. Dovrai anche implementare la funzionalità per moltiplicare i numeri a 128 bit.

Spero che questo aiuti.

/A.B.

fonte

2009-11-27 13:45:46

risposta

Problemi correlati