Come implementare la divisione lunga per numeri enormi (bignums)

Question

Sto cercando di implementare la divisione lunga per bignums. Sfortunatamente non posso usare una libreria come GMP a causa delle limitazioni della programmazione incorporata. Inoltre, voglio l'esercizio intellettuale di imparare come implementarlo. Finora ho aggiunto addizioni e moltiplicazioni usando matrici di byte di lunghezza qualsiasi (quindi ogni byte è come una cifra base di 256).

Sto solo cercando di iniziare a implementare la divisione/modulo e voglio sapere da dove cominciare? Ho trovato un sacco di codice altamente ottimizzato (noto anche come illeggibile) sulla rete, che non mi aiuta, e ho trovato molti white paper matematici altamente tecnici dai quali non posso colmare il divario tra teoria e implementazione .

Se qualcuno potrebbe consigliare un algoritmo popolare e indicarmi una spiegazione semplice e comprensibile che si spinge verso l'implessività, sarebbe fantastico.

-edit: ho bisogno di algoritmi che il lavoro quando il dividendo è ~ 4000bits, e divisore è ~ 2000bits

-edit: Sarà questo lavoro algoritmo con base-256? http://courses.cs.vt.edu/~cs1104/BuildingBlocks/divide.030.html

-edit: È questo l'algoritmo (divisione newton) che dovrei usare davvero? http://en.wikipedia.org/wiki/Division_(digital)#Newton.E2.80.93Raphson_division

Answer 1

Se si desidera imparare, quindi iniziare con il metodo di carta e matita utilizzato nella scuola elementare. Che ci crediate o no, questo è essenzialmente lo stesso algoritmo di O (n^2) che è usato nella maggior parte delle librerie di bignum per i numeri che sono nella gamma che state cercando. Il difficile primo passo è chiamato "stima del quoziente" e probabilmente sarà il più difficile da comprendere. Una volta capito questo, il resto dovrebbe venire facile.

Un buon riferimento è "Algoritmi Seminumerici" di Knuth. Ha molte discussioni sui diversi modi di fare la stima del quoziente sia nel testo che negli esercizi. Quel libro ha capitoli dedicati alle implementazioni di bignum.

Answer 2

Questa domanda ha più di 2 anni, ma per i numeri di questa dimensione è possibile consultare il codice sorgente OpenSSL. Rende RSA con questi numeri di dimensioni, quindi ha un sacco di routine matematiche ottimizzate per numeri da 1000 a 4000 bit.

Answer 3

Stai usando il codice Four1 (long double [], int, int) nel tuo codice e poi convolvi e poi esegui una trasformazione inversa bene ho ottenuto la moltiplicazione per funzionare ma quando ho provato a fare la divisione nello stesso modo in cui sputa fuori un risultato quindi esci quindi non posso fare a meno ma se hai il tomo chiamato "Ricette numeriche in C++" vai verso la fine e troverai ciò che stai cercando in realtà inizia da pagina 916 a 926.