Spiegazione aritmetica a precisione arbitraria

StackOverflow https://stackoverflow.com/questions/1218149

  •  10-07-2019
  •  | 
  •  

Domanda

Sto cercando di imparare il C e mi sono imbattuto nell'incapacità di lavorare con numeri VERAMENTE grandi (ad esempio 100 cifre, 1000 cifre, ecc.).Sono consapevole che esistono librerie per farlo, ma voglio tentare di implementarlo da solo.

Voglio solo sapere se qualcuno ha o può fornire una spiegazione molto dettagliata e banale dell'aritmetica a precisione arbitraria.

È stato utile?

Soluzione

È tutta una questione di archiviazione adeguata e algoritmi per trattare i numeri come parti più piccole.Supponiamo che tu abbia un compilatore in cui an int può essere solo compreso tra 0 e 99 e desideri gestire numeri fino a 999999 (qui ci preoccuperemo solo dei numeri positivi per semplicità).

Lo fai assegnando a ciascun numero tre ints e utilizzando le stesse regole che (avresti dovuto) imparare alle elementari per addizioni, sottrazioni e le altre operazioni di base.

In una libreria di precisione arbitraria, non esiste un limite fisso al numero di tipi di base utilizzati per rappresentare i nostri numeri, ma solo quello che la memoria può contenere.

Aggiunta ad esempio: 123456 + 78:

12 34 56
      78
-- -- --
12 35 34

Lavorando dall'estremità meno significativa:

  • riporto iniziale = 0.
  • 56 + 78 + 0 riporto = 134 = 34 con 1 riporto
  • 34 + 00 + 1 riporto = 35 = 35 con 0 riporto
  • 12 + 00 + 0 riporto = 12 = 12 con 0 riporto

Questo è, infatti, il modo in cui l'addizione generalmente funziona a livello di bit all'interno della CPU.

La sottrazione è simile (usando la sottrazione del tipo base e prendendo in prestito invece del riporto), la moltiplicazione può essere eseguita con addizioni ripetute (molto lente) o prodotti incrociati (più veloci) e la divisione è più complicata ma può essere eseguita spostando e sottraendo i numeri coinvolti (la lunga divisione che avresti imparato da bambino).

In realtà ho scritto librerie per fare questo genere di cose utilizzando le potenze massime di dieci che possono essere inserite in un numero intero al quadrato (per evitare overflow quando si moltiplicano due intinsieme, ad esempio un file a 16 bit int essendo limitato da 0 a 99 per generare 9.801 (<32.768) al quadrato o 32 bit int utilizzando da 0 a 9.999 per generare 99.980.001 (<2.147.483.648)), il che ha notevolmente facilitato gli algoritmi.

Alcuni trucchi a cui prestare attenzione.

1/ Quando aggiungi o moltiplichi numeri, preassegna lo spazio massimo necessario, quindi riducilo in seguito se ritieni che sia troppo.Ad esempio, aggiungendo due "cifre" da 100 (dove cifra è un int) i numeri non ti daranno mai più di 101 cifre.Moltiplicare un numero di 12 cifre per un numero di 3 cifre non genererà mai più di 15 cifre (aggiungere i conteggi delle cifre).

2/ Per una maggiore velocità, normalizza (riduci lo spazio di archiviazione richiesto per) i numeri solo se assolutamente necessario: la mia libreria lo aveva come chiamata separata in modo che l'utente possa decidere tra problemi di velocità e archiviazione.

3/ L'addizione di un numero positivo e negativo è una sottrazione, e sottrarre un numero negativo equivale ad aggiungere il positivo equivalente.Puoi risparmiare un bel po' di codice facendo in modo che i metodi di aggiunta e sottrazione si richiamino tra loro dopo aver regolato i segni.

4/ Evita di sottrarre numeri grandi da quelli piccoli poiché ti ritroverai invariabilmente con numeri come:

         10
         11-
-- -- -- --
99 99 99 99 (and you still have a borrow).

Invece, sottrai 10 da 11, quindi negalo:

11
10-
--
 1 (then negate to get -1).

Ecco i commenti (trasformati in testo) da una delle biblioteche per cui ho dovuto farlo.Sfortunatamente il codice stesso è protetto da copyright, ma potresti essere in grado di raccogliere informazioni sufficienti per gestire le quattro operazioni di base.Supponiamo di seguito che -a E -b rappresentano numeri negativi e a E b sono zero o numeri positivi.

Per aggiunta, se i segni sono diversi, utilizzare la sottrazione della negazione:

-a +  b becomes b - a
 a + -b becomes a - b

Per sottrazione, se i segni sono diversi, utilizzare l'aggiunta della negazione:

 a - -b becomes   a + b
-a -  b becomes -(a + b)

Anche una gestione speciale per garantire la sottrazione di numeri piccoli da quelli grandi:

small - big becomes -(big - small)

Moltiplicazione utilizza la matematica entry-level come segue:

475(a) x 32(b) = 475 x (30 + 2)
               = 475 x 30 + 475 x 2
               = 4750 x 3 + 475 x 2
               = 4750 + 4750 + 4750 + 475 + 475

Il modo in cui ciò viene ottenuto prevede l'estrazione di ciascuna delle cifre di 32 una alla volta (all'indietro) quindi l'utilizzo dell'addizione per calcolare un valore da aggiungere al risultato (inizialmente zero).

ShiftLeft E ShiftRight le operazioni vengono utilizzate per moltiplicare o dividere rapidamente a LongInt dal valore di wrap (10 per la matematica "reale").Nell'esempio sopra, aggiungiamo 475 a zero 2 volte (l'ultima cifra di 32) per ottenere 950 (risultato = 0 + 950 = 950).

Poi abbiamo lasciato lo spostamento 475 per ottenere 4750 e lo spostamento a destra 32 per ottenere 3.Aggiungi 4750 a zero 3 volte per ottenere 14250 quindi aggiungi il risultato di 950 per ottenere 15200.

Scorri a sinistra 4750 per ottenere 47500, sposta a destra 3 per ottenere 0.Poiché il 32 spostato a destra ora è zero, abbiamo finito e, infatti, 475 x 32 equivale a 15200.

Divisione è anch'esso complicato ma basato sull'aritmetica antica (il metodo "gazinta" per "entra").Considera la seguente lunga divisione per 12345 / 27:

       457
   +-------
27 | 12345    27 is larger than 1 or 12 so we first use 123.
     108      27 goes into 123 4 times, 4 x 27 = 108, 123 - 108 = 15.
     ---
      154     Bring down 4.
      135     27 goes into 154 5 times, 5 x 27 = 135, 154 - 135 = 19.
      ---
       195    Bring down 5.
       189    27 goes into 195 7 times, 7 x 27 = 189, 195 - 189 = 6.
       ---
         6    Nothing more to bring down, so stop.

Perciò 12345 / 27 È 457 con resto 6.Verificare:

  457 x 27 + 6
= 12339    + 6
= 12345

Ciò viene implementato utilizzando una variabile di prelievo (inizialmente zero) per ridurre i segmenti di 12345 uno alla volta finché non diventa maggiore o uguale a 27.

Quindi sottraiamo semplicemente 27 da questo finché non arriviamo al di sotto di 27: il numero di sottrazioni è il segmento aggiunto alla riga superiore.

Quando non ci sono più segmenti da abbattere, abbiamo il nostro risultato.

Tieni presente che questi sono algoritmi piuttosto semplici.Esistono modi molto migliori per eseguire operazioni aritmetiche complesse se i tuoi numeri saranno particolarmente grandi.Puoi esaminare qualcosa del genere Libreria aritmetica a precisione multipla GNU - è sostanzialmente migliore e più veloce delle mie librerie.

Ha lo sfortunato inconveniente di uscire semplicemente se esaurisce la memoria (un difetto piuttosto fatale per una libreria di uso generale secondo me) ma, se riesci a guardare oltre, è abbastanza buono in quello che fa.

Se non puoi usarlo per motivi di licenza (o perché non vuoi che la tua applicazione esca senza una ragione apparente), potresti almeno ottenere da lì gli algoritmi da integrare nel tuo codice.

Ho anche scoperto che i corpi laggiù MPIR (un fork di GMP) sono più disponibili alle discussioni su potenziali cambiamenti: sembrano un gruppo più favorevole agli sviluppatori.

Altri suggerimenti

Mentre reinventare la ruota è estremamente utile per l'edificazione e l'apprendimento personale, è anche un compito estremamente grande. Non voglio dissuaderti dal momento che è un esercizio importante e uno che ho fatto da solo, ma dovresti essere consapevole che ci sono problemi sottili e complessi che i pacchetti più grandi affrontano.

Ad esempio, moltiplicazione. Ingenuamente, potresti pensare al metodo "scolaro", cioè scrivere un numero sopra l'altro, quindi fare una lunga moltiplicazione come hai imparato a scuola. Esempio: 

      123
    x  34
    -----
      492
+    3690
---------
     4182

ma questo metodo è estremamente lento (O (n ^ 2), n è il numero di cifre). Invece, i moderni pacchetti bignum usano una trasformata discreta di Fourier o una trasformata numerica per trasformarla in un'operazione essenzialmente O (n ln (n)).

E questo è solo per numeri interi. Quando entri in funzioni più complicate su un tipo di rappresentazione reale del numero (log, sqrt, exp, ecc.) Le cose diventano ancora più complicate.

Se desideri un background teorico, ti consiglio vivamente di leggere il primo capitolo del libro di Yap, " Problemi fondamentali dell'algebra algoritmica " . Come già accennato, la libreria gmp bignum è una libreria eccellente. Per i numeri reali, ho usato mpfr e mi è piaciuto.

Non reinventare la ruota: potrebbe rivelarsi quadrata!

Utilizza una libreria di terze parti, come GNU MP , che è stata testata.

Lo fai praticamente nello stesso modo in cui lo fai con carta e matita ...

  • Il numero deve essere rappresentato in un buffer (array) in grado di assumere una dimensione arbitraria (il che significa utilizzare malloc e realloc) secondo necessità
  • implementate il più possibile l'aritmetica di base usando strutture supportate dal linguaggio e gestite i carry e spostate manualmente il punto di radix
  • scruti testi di analisi numerica per trovare argomenti efficaci per gestire funzioni più complesse
  • implementate solo tutto il necessario.

In genere si utilizzerà come unità di calcolo di base

  • byte contenenti con 0-99 o 0-255
  • Parole a 16 bit contente tra 0-9999 o 0--65536
  • parole a 32 bit contenenti ...
  • ...

come dettato dalla tua architettura.

La scelta della base binaria o decimale dipende dai desideri dell'utente per la massima efficienza nello spazio, la leggibilità umana e la presenza di assenza di supporto matematico binario con codice decimale (BCD) sul chip.

Puoi farlo con il livello di matematica delle superiori. Sebbene nella realtà vengano utilizzati algoritmi più avanzati. Ad esempio, per aggiungere due numeri da 1024 byte: 

unsigned char first[1024], second[1024], result[1025];
unsigned char carry = 0;
unsigned int  sum   = 0;

for(size_t i = 0; i < 1024; i++)
{
    sum = first[i] + second[i] + carry;
    carry = sum - 255;
}

il risultato dovrà essere maggiore di one place in caso di aggiunta per occuparsi dei valori massimi. Guarda questo: 

9
   +
9
----
18

TTMath è un'ottima libreria se vuoi imparare. È costruito usando C ++. L'esempio sopra è stato uno sciocco, ma è così che si sommano e si sottraggono in generale!

Un buon riferimento all'argomento è Complessità computazionale delle operazioni matematiche . Ti dice quanto spazio è necessario per ogni operazione che vuoi implementare. Ad esempio, se si hanno due N-digit numeri, è necessario 2N digits per memorizzare il risultato della moltiplicazione.

Come diceva Mitch , non è di gran lunga un compito facile da implementare! Ti consiglio di dare un'occhiata a TTMath se conosci C ++.

Uno dei riferimenti finali (IMHO) è il Volume II del TAOCP di Knuth. Spiega molti algoritmi per rappresentare numeri e operazioni aritmetiche su queste rappresentazioni. 

@Book{Knuth:taocp:2,
   author    = {Knuth, Donald E.},
   title     = {The Art of Computer Programming},
   volume    = {2: Seminumerical Algorithms, second edition},
   year      = {1981},
   publisher = {\Range{Addison}{Wesley}},
   isbn      = {0-201-03822-6},
}

Supponendo che tu voglia scrivere tu stesso un grande codice intero, questo può essere sorprendentemente semplice da fare, parlato come qualcuno che lo ha fatto di recente (anche se in MATLAB.) Ecco alcuni dei trucchi che ho usato:

  • Ho memorizzato ogni singola cifra decimale come doppio numero. Ciò semplifica molte operazioni, in particolare l'output. Sebbene occupi più spazio di quanto potresti desiderare, la memoria qui è economica e rende la moltiplicazione molto efficiente se riesci a contrapporre una coppia di vettori in modo efficiente. In alternativa, puoi memorizzare diverse cifre decimali in una doppia, ma attenzione quindi che la convoluzione per eseguire la moltiplicazione può causare problemi numerici su numeri molto grandi.

  • Memorizza un bit di segno separatamente.

  • L'aggiunta di due numeri è principalmente una questione di aggiunta delle cifre, quindi verifica la presenza di un carry ad ogni passaggio.

  • La moltiplicazione di una coppia di numeri viene eseguita meglio come convoluzione seguita da una fase di carry, almeno se si dispone di un codice di convoluzione veloce alla spina.

  • Anche quando si memorizzano i numeri come una stringa di singole cifre decimali, nel risultato è possibile eseguire la divisione (anche mod / rem ops) per ottenere circa 13 cifre decimali alla volta. Questo è molto più efficiente di una divisione che funziona solo con una cifra decimale alla volta.

  • Per calcolare la potenza di un numero intero, calcolare la rappresentazione binaria dell'esponente. Quindi utilizzare ripetute operazioni di quadratura per calcolare i poteri secondo necessità.

  • Molte operazioni (factoring, test di primalità, ecc.) trarranno beneficio da un'operazione powermod. Cioè, quando si calcola mod (a ^ p, N), si riduce il risultato mod N ad ogni passo dell'espiazione in cui p è stato espresso in forma binaria. Non calcolare prima a ^ p, quindi provare a ridurlo mod N.

Ecco un semplice (ingenuo) esempio che ho fatto in PHP.

Ho implementato " Aggiungi " e " Moltiplica " e l'ho usato per un esempio di esponente.

http://adevsoft.com/simple-php -arbitrary-precisione-intero-big-num-esempio /

Code snip 

// Add two big integers
function ba($a, $b)
{
    if( $a === "0" ) return $b;
    else if( $b === "0") return $a;

    $aa = str_split(strrev(strlen($a)>1?ltrim($a,"0"):$a), 9);
    $bb = str_split(strrev(strlen($b)>1?ltrim($b,"0"):$b), 9);
    $rr = Array();

    $maxC = max(Array(count($aa), count($bb)));
    $aa = array_pad(array_map("strrev", $aa),$maxC+1,"0");
    $bb = array_pad(array_map("strrev", $bb),$maxC+1,"0");

    for( $i=0; $i<=$maxC; $i++ )
    {
        $t = str_pad((string) ($aa[$i] + $bb[$i]), 9, "0", STR_PAD_LEFT);

        if( strlen($t) > 9 )
        {
            $aa[$i+1] = ba($aa[$i+1], substr($t,0,1));
            $t = substr($t, 1);
        }

        array_unshift($rr, $t);
     }

     return implode($rr);
}
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top