Come dividere i grandi numeri?

Question

Ho un grande numero (intero, senza segno) memorizzato in 2 variabili (come puoi vedere, la parte alta e bassa del numero):

unsigned long long int high;
unsigned long long int low;

So come aggiungere o sottrarre qualche altro tipo di variabile.

Ma devo dividere quel tipo di numeri. Come farlo? Lo so, posso sottrarre N volte, ma, forse, ci sono soluzioni migliori. ; -)

Lingua: C

Answer 1

Sì. Implica turni, e non lo consiglio di farlo in C. Questo è uno di quei rari esempi in cui l'assemblatore può ancora dimostrare il suo valore, facendo funzionare le cose centinaia di volte più velocemente (E non penso di esagerare questo.)

Non rivendico la totale correttezza, ma quanto segue dovrebbe farti andare:

(1) Inizializza il risultato su zero.

(2) Sposta il divisore di quanti più bit possibile a sinistra, senza lasciarlo diventare maggiore del dividendo.

(3) Sottrai il divisore spostato dal dividendo e aggiungine uno al risultato.

(4) Ora sposta il divisore verso destra fino a quando ancora una volta, è inferiore al dividendo rimanente, e per ogni spostamento a destra, il risultato dello spostamento a sinistra di un bit. Torna a (3) a meno che non sia soddisfatta la condizione di arresto. (La condizione di arresto deve essere qualcosa come "divisore è diventato zero", ma non ne sono sicuro.)

È davvero bello tornare ad alcuni REALI problemi di programmazione :-)

Answer 2

Hai esaminato librerie di grandi numeri, come GNU MP BigNum ?

Answer 3

  

Lo so, posso sottrarre N volte, ma forse ci sono soluzioni migliori.

La sottrazione di N volte può essere lenta quando N è grande.

Meglio (cioè più complicato ma più veloce) sarebbe shift-and-sottrarre, usando l'algoritmo che hai imparato a fare lunga divisione dei numeri decimali nella scuola elementare.

[Potrebbe esserci anche una libreria di terze parti e / o supporto specifico del compilatore per tali numeri.]

Answer 4

Hmm. Suppongo che se hai un po 'di margine in "alto", puoi spostarlo tutto in alto di una cifra, dividere in alto per il numero, quindi aggiungere il resto alla cifra rimanente in alto in basso e dividere in basso per il numero, quindi spostare tutto indietro .

Answer 5

Ecco un'altra libreria che esegue aritmetica a 128 bit. GnuCash: Math128 .

Answer 6

Secondo i miei commentatori di seguito, la mia risposta precedente era stupida.

Rapidamente, la mia nuova risposta sarebbe che quando ho provato a farlo in passato, comportava quasi sempre lo spostamento, perché è l'unica operazione che può essere applicata su più "parole", se vuoi, e avere lo stesso aspetto di una parola di grandi dimensioni (con l'eccezione di dover tenere traccia dei bit di carryover).

Esistono un paio di approcci diversi, ma non conosco una direzione generale migliore rispetto all'utilizzo dei turni, a meno che il tuo hardware non abbia alcune operazioni speciali.

Answer 7

Puoi implementare un " BigInt " algoritmo di tipo che esegue divisioni su array di stringhe. Crea 1 array di stringhe per ogni coppia alta e bassa ed esegui la divisione. Memorizza il risultato in un altro array di stringhe, quindi converti nuovamente in coppia intera alta e bassa.

Poiché il linguaggio è C, l'array sarebbe probabilmente un array di caratteri. Consideralo analogo alla "stringa array" " Stavo citando sopra.

Answer 8

Puoi fare l'aggiunta e la sottrazione di oggetti binari arbitrariamente grandi usando il ciclo dell'assemblatore e " aggiungi / sottragga con carry (adc / sbb) " Istruzioni. È possibile implementare le altre operazioni utilizzandole. Non ho mai indagato facendo qualcosa oltre quei due personalmente.

Answer 9

Se il tuo processore (o la tua libreria C) ha una divisione veloce a 64 bit, puoi dividere la divisione a 128 bit in pezzi (allo stesso modo in cui faresti una divisione a 32 bit su processori che avevano 16 bit divisioni).

A proposito, ci sono tutti i tipi di trucchi che puoi usare se sai quali saranno i valori tipici per il dividendo e il divisore. Qual è la fonte di questi numeri? Se molti dei tuoi casi possono essere risolti rapidamente, potrebbe andare bene il caso occasionale richiede molto tempo.

Inoltre, se riesci a trovare casi in cui una risposta approssimativa è OK, questo apre la porta a molte approssimazioni veloci.