Volevo sapere come sono implementati BigInt e altre cose simili. Ho provato a verificare il codice sorgente JAVA, ma per me era tutto greco e latino. Puoi per favore spiegarmi l'algo in parole - nessun codice, in modo che io capisca cosa sto effettivamente usando quando uso qualcosa dall'API JAVA. salutiCome funzionano le implementazioni di BigNums?
Concettualmente, nello stesso modo in cui si eseguono aritmetiche di dimensioni arbitrarie a mano. Hai qualcosa come una matrice di valori e algoritmi per le varie operazioni che funzionano sull'array.
Dire di voler aggiungere 100 a 901. Si inizia con i due numeri come array:
[0, 1, 0, 0]
[0, 9, 0, 1]
Quando si aggiunge, l'algoritmo inoltre parte dalla destra, prende 0+1, dando 1, 0+0, dando 0, e - ora la parte difficile - 9+1 dà 10, ma ora dobbiamo portarlo, quindi aggiungiamo 1 alla colonna successiva e inseriamo (9+1)%10 nella terza colonna.
Quando i tuoi numeri crescono abbastanza (superiori a 9999 in questo esempio), devi allocare più spazio in qualche modo.
Questo è, naturalmente, un po 'semplificato se si memorizzano i numeri in in ordine inverso.
Le implementazioni reali utilizzano parole complete, quindi il modulo è in realtà una grande potenza di due, ma il concetto è lo stesso.
C'è una sezione molto buona su questo in Knuth.
grazie mille :) – shahensha
C'è anche una sezione in Numerical Recipes (che segue da vicino Knuth). La parte difficile è ottenere la moltiplicazione giusta. L'algoritmo scolastico non scala molto bene, quindi usi trucchi (ad esempio FFT). Una volta che hai moltiplicato, puoi esprimere molte cose con esso. –