Come gestire numeri interi arbitrariamente grandi

Question

Sto lavorando su un linguaggio di programmazione e oggi ho ottenuto il punto in cui avrei potuto compilare la funzione fattoriale (ricorsiva), tuttavia a causa della dimensione massima di un numero intero il più grande che posso ottenere è fattoriale (12). Quali sono alcune tecniche per gestire gli interi di una dimensione massima arbitraria. La lingua attualmente funziona traducendo il codice in C++.

Answer 1

Se sono necessari più di 32 bit, è possibile considerare l'utilizzo di numeri interi a 64 bit (lunghi a lungo) oppure utilizzare o scrivere una libreria matematica di precisione arbitraria, ad es. GNU MP.

Answer 2

Non c'è un modo semplice per farlo in C++. Dovrai utilizzare una libreria esterna come GNU Multiprecision o utilizzare un linguaggio diverso che supporti in modo nativo interi interi arbitrariamente grandi come Python.

Answer 3

Altri poster hanno fornito collegamenti a librerie che faranno questo per voi, ma sembra che stiate cercando di farlo nella vostra lingua. Il mio primo pensiero è: sei sicuro di aver bisogno di farlo? La maggior parte delle lingue usa una libreria aggiuntiva come altri hanno suggerito.

Supponendo che si stia scrivendo un compilatore e questa funzione sia necessaria, è possibile implementare funzioni aritmetiche intere per valori arbitrariamente grandi in assembly.

Ad esempio, un'implementazione semplice (ma non ottimale) rappresenterebbe i numeri come decimale codificato in binario. Le funzioni aritmetiche potrebbero utilizzare gli stessi algoritmi che usereste se steste facendo la matematica con carta e penna.

Inoltre, considerare l'utilizzo di un tipo di dati specializzato per questi numeri interi di grandi dimensioni. In questo modo gli interi "normali" possono utilizzare l'aritmetica standard a 32 bit.

Answer 4

Il mio approccio preferibile sarebbe quello di utilizzare il mio tipo int corrente per 32 bit (o magari cambiarlo internamente per essere un long long o alcuni di essi, purché possa continuare ad utilizzare gli stessi algoritmi), quindi quando trabocca, passa alla memorizzazione come bignum, sia della mia creazione che dell'uso di una libreria esterna. Tuttavia, ho l'impressione che avrei bisogno di controllare l'overflow su ogni singola operazione aritmetica, circa 2 volte al di sopra delle operazioni aritmetiche. Come potrei risolverlo?

Answer 5

Se stai costruendo questo in una lingua (a fini di apprendimento, suppongo), penso che probabilmente scriverei una piccola libreria BCD. Basta memorizzare i tuoi numeri BCD all'interno di matrici di byte.

In effetti, con le gigantesche capacità di archiviazione odierne, si potrebbe semplicemente utilizzare un array di byte in cui ogni byte contiene solo una cifra (0-9). Quindi scrivi la tua routine per aggiungere, sottrarre, moltiplicare e dividere i tuoi array di byte.

(Divide è il disco uno, ma scommetto è possibile trovare qualche codice là fuori da qualche parte.)

posso darvi qualche psuedocodarlo Java-like, ma non posso davvero fare C++ da zero a questo punto:

class BigAssNumber { 
    private byte[] value; 

    // This constructor can handle numbers where overflows have occurred. 
    public BigAssNumber(byte[] value) { 
     this.value=normalize(value); 
    } 

    // Adds two numbers and returns the sum. Originals not changed. 
    public BigAssNumber add(BigAssNumber other) { 
     // This needs to be a byte by byte copy in newly allocated space, not pointer copy! 
     byte[] dest = value.length > other.length ? value : other.value;   

     // Just add each pair of numbers, like in a pencil and paper addition problem. 
     for(int i=0; i<min(value.length, other.value.length); i++) 
      dest[i]=value[i]+other.value[i]; 

     // constructor will fix overflows. 
     return new BigAssNumber(dest); 
    } 

    // Fix things that might have overflowed 0,17,22 will turn into 1,9,2   
    private byte[] normalize(byte [] value) { 
     if (most significant digit of value is not zero) 
      extend the byte array by a few zero bytes in the front (MSB) position. 

     // Simple cheap adjust. Could lose inner loop easily if It mattered. 
     for(int i=0;i<value.length;i++) 
      while(value[i] > 9) { 
       value[i] -=10; 
       value[i+1] +=1; 
      } 
     } 
    } 
} 

utilizzare il fatto che abbiamo un sacco di spazio in più in un byte per contribuire ad affrontare overflow aggiunta in modo generico. Può funzionare anche per la sottrazione e aiutare in alcuni modi.

Answer 6

Se si desidera eseguire il rollover della propria libreria di precisione arbitraria, vedere Algoritmi seminumerici di Knuth, volume 2 del suo opus magnum.

Answer 7

Se implementassi la mia lingua e volessi supportare numeri di lunghezza arbitrari, userò una lingua di destinazione con il concetto di carry/borrow.Ma dal momento che non esiste un HLL che implementa questo senza gravi implicazioni sulle prestazioni (come le eccezioni), certamente lo implementerò in assembly. Probabilmente richiederà una singola istruzione (come in JC in x86) per controllare l'overflow e gestirlo (come in ADC in x86), che è un compromesso accettabile per una lingua che implementa precisione arbitraria. Quindi userò alcune funzioni scritte in assembly invece di operatori regolari, se è possibile utilizzare l'overloading per un output più elegante, ancora meglio. Ma non mi aspetto che il C++ generato sia mantenibile (o inteso a essere mantenuto) come lingua di arrivo.

Oppure, basta usare una libreria che ha più campane e fischi del necessario e usarla per tutti i tuoi numeri.

Come approccio ibrido, rilevare l'overflow in assembly e chiamare la funzione di libreria in caso di overflow anziché eseguire il rollover della propria mini library.