Arithmetik mit beliebiger Genauigkeit Erläuterung

Ich versuche C zu lernen und bin auf die Unfähigkeit gestoßen, mit WIRKLICH großen Zahlen (dh 100 Ziffern, 1000 Ziffern usw.) zu arbeiten. Ich bin mir bewusst, dass es dafür Bibliotheken gibt, aber ich möchte versuchen, es selbst zu implementieren.

Ich möchte nur wissen, ob jemand eine sehr detaillierte, heruntergekommene Erklärung der Arithmetik mit beliebiger Genauigkeit hat oder liefern kann.

Es ist alles eine Frage des angemessenen Speichers und der Algorithmen, um Zahlen als kleinere Teile zu behandeln. Nehmen wir an, Sie haben einen Compiler, in dem ein intnur 0 bis 99 sein kann, und Sie möchten Zahlen bis 999999 verarbeiten (wir werden uns hier nur um positive Zahlen kümmern, um es einfach zu halten).

Sie tun dies, indem Sie jeder Zahl drei intSekunden geben und dieselben Regeln anwenden, die Sie in der Grundschule für Addition, Subtraktion und die anderen Grundoperationen gelernt haben (sollten).

In einer Bibliothek mit beliebiger Genauigkeit gibt es keine feste Begrenzung für die Anzahl der Basistypen, die zur Darstellung unserer Zahlen verwendet werden, unabhängig davon, welchen Speicher der Speicher aufnehmen kann.

Ergänzung zum Beispiel 123456 + 78::

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

Arbeiten vom am wenigsten signifikanten Ende:

• anfänglicher Übertrag = 0.
• 56 + 78 + 0 Übertrag = 134 = 34 mit 1 Übertrag
• 34 + 00 + 1 Übertrag = 35 = 35 mit 0 Übertrag
• 12 + 00 + 0 Übertrag = 12 = 12 mit 0 Übertrag

Auf diese Weise funktioniert das Hinzufügen im Allgemeinen auf Bitebene in Ihrer CPU.

Die Subtraktion ist ähnlich (unter Verwendung der Subtraktion des Basistyps und Ausleihen anstelle des Übertrags), die Multiplikation kann mit wiederholten Additionen (sehr langsam) oder Kreuzprodukten (schneller) erfolgen, und die Division ist schwieriger, kann jedoch durch Verschieben und Subtrahieren der Zahlen erfolgen beteiligt (die lange Teilung, die Sie als Kind gelernt hätten).

Ich habe tatsächlich Bibliotheken geschrieben, um diese Art von Dingen mit den maximalen Zehnerpotenzen zu erledigen, die im Quadrat in eine Ganzzahl eingepasst werden können (um einen Überlauf beim Multiplizieren von zwei ints zu verhindern , z. B. wenn ein 16-Bit intauf 0 bis 99 begrenzt ist Generieren Sie 9.801 (<32.768) im Quadrat oder 32-Bit intmit 0 bis 9.999, um 99.980.001 (<2.147.483.648) zu generieren, was die Algorithmen erheblich vereinfacht.

Einige Tricks, auf die Sie achten sollten.

1 / Wenn Sie Zahlen hinzufügen oder multiplizieren, weisen Sie den maximal benötigten Speicherplatz vorab zu und reduzieren Sie ihn später, wenn Sie feststellen, dass er zu groß ist. Wenn Sie beispielsweise zwei 100-stellige intZahlen (wobei die Ziffer eine ist ) hinzufügen , erhalten Sie nie mehr als 101 Ziffern. Das Multiplizieren einer 12-stelligen Zahl mit einer 3-stelligen Zahl erzeugt niemals mehr als 15 Stellen (addieren Sie die Ziffernzahlen).

2 / Um die Geschwindigkeit zu erhöhen, normalisieren (reduzieren Sie den dafür erforderlichen Speicherplatz) die Nummern nur, wenn dies unbedingt erforderlich ist. Meine Bibliothek hatte dies als separaten Aufruf, damit der Benutzer zwischen Geschwindigkeits- und Speicherproblemen entscheiden kann.

3 / Die Addition einer positiven und einer negativen Zahl ist eine Subtraktion, und die Subtraktion einer negativen Zahl entspricht der Addition der äquivalenten positiven Zahl. Sie können eine Menge Code sparen, indem Sie sich nach dem Anpassen der Vorzeichen gegenseitig aufrufen und subtrahieren lassen.

4 / Vermeiden Sie es, große Zahlen von kleinen zu subtrahieren, da Sie immer Zahlen wie:

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

Subtrahieren Sie stattdessen 10 von 11 und negieren Sie es dann:

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

Hier sind die Kommentare (in Text umgewandelt) aus einer der Bibliotheken, für die ich dies tun musste. Der Code selbst ist leider urheberrechtlich geschützt, aber Sie können möglicherweise genügend Informationen auswählen, um die vier grundlegenden Vorgänge auszuführen. Nehmen Sie im Folgenden an, dass -aund -bnegative Zahlen darstellen und aund bNull oder positive Zahlen sind.

Für hinaus , wenn Anzeichen sind unterschiedlich, Verwendung Subtraktion der Negation:

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

Für Subtraktion , wenn Anzeichen sind unterschiedlich, Verwendung Zugabe der Negation:

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

Auch spezielle Behandlung, um sicherzustellen, dass wir kleine Zahlen von großen subtrahieren:

small - big becomes -(big - small)

Bei der Multiplikation wird die Einstiegsmathematik wie folgt verwendet:

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

Die Art und Weise, wie dies erreicht wird, besteht darin, jede der Ziffern von 32 einzeln (rückwärts) zu extrahieren und dann mit add einen Wert zu berechnen, der dem Ergebnis hinzugefügt werden soll (anfänglich Null).

ShiftLeftund ShiftRightOperationen werden verwendet, um a schnell LongIntmit dem Wrap-Wert zu multiplizieren oder zu dividieren (10 für "echte" Mathematik). Im obigen Beispiel addieren wir 475 zweimal zu Null (die letzte Ziffer von 32), um 950 zu erhalten (Ergebnis = 0 + 950 = 950).

Dann haben wir die Schicht 475 verlassen, um 4750 zu erhalten, und die rechte Schicht 32, um 3 zu erhalten. Addiere 4750 dreimal zu Null, um 14250 zu erhalten, und addiere dann zum Ergebnis von 950, um 15200 zu erhalten.

Linksverschiebung 4750, um 47500 zu erhalten, Rechtsverschiebung 3, um 0 zu erhalten. Da die rechtsverschobene 32 jetzt Null ist, sind wir fertig und tatsächlich entspricht 475 x 32 15200.

Die Division ist ebenfalls schwierig, basiert jedoch auf früher Arithmetik (die "Gazinta" -Methode für "geht hinein"). Betrachten Sie die folgende lange Unterteilung für 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.

Daher 12345 / 27ist 457mit Rest 6. Überprüfen:

  457 x 27 + 6
= 12339    + 6
= 12345

Dies wird implementiert, indem eine Drawdown-Variable (anfänglich Null) verwendet wird, um die Segmente von 12345 einzeln zu senken, bis sie größer oder gleich 27 sind.

Dann subtrahieren wir einfach 27 davon, bis wir unter 27 kommen - die Anzahl der Subtraktionen ist das Segment, das der obersten Zeile hinzugefügt wird.

Wenn es keine Segmente mehr zu stürzen gibt, haben wir unser Ergebnis.

Denken Sie daran, dies sind ziemlich grundlegende Algorithmen. Es gibt weitaus bessere Möglichkeiten, komplexe Arithmetik durchzuführen, wenn Ihre Zahlen besonders groß sein sollen. Sie können sich so etwas wie die GNU Multiple Precision Arithmetic Library ansehen - sie ist wesentlich besser und schneller als meine eigenen Bibliotheken.

Es hat die eher unglückliche Fehlfunktion, dass es einfach beendet wird, wenn der Speicher knapp wird (ein ziemlich schwerwiegender Fehler für eine Allzweckbibliothek meiner Meinung nach), aber wenn Sie darüber hinausblicken können, ist es ziemlich gut darin, was es tut.

Wenn Sie es aus Lizenzgründen nicht verwenden können (oder weil Sie nicht möchten, dass Ihre Anwendung ohne ersichtlichen Grund beendet wird), können Sie zumindest die Algorithmen von dort für die Integration in Ihren eigenen Code erhalten.

Ich habe auch festgestellt, dass die Köpfe bei MPIR (eine Gabelung von GMP) für Diskussionen über mögliche Änderungen zugänglicher sind - sie scheinen entwicklerfreundlicher zu sein.

Die Neuerfindung des Rades ist zwar sehr gut für Ihre persönliche Erbauung und Ihr Lernen, aber auch eine äußerst große Aufgabe. Ich möchte Sie nicht davon abhalten, eine wichtige Übung zu sein, die ich selbst gemacht habe, aber Sie sollten sich bewusst sein, dass bei der Arbeit subtile und komplexe Probleme auftreten, mit denen sich größere Pakete befassen.

Zum Beispiel Multiplikation. Naiv könnten Sie an die 'Schüler'-Methode denken, dh eine Zahl über die andere schreiben und dann eine lange Multiplikation durchführen, wie Sie in der Schule gelernt haben. Beispiel:

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

Diese Methode ist jedoch extrem langsam (O (n ^ 2), wobei n die Anzahl der Stellen ist). Stattdessen verwenden moderne Bignum-Pakete entweder eine diskrete Fourier-Transformation oder eine numerische Transformation, um dies in eine im Wesentlichen O (n ln (n)) -Operation umzuwandeln.

Und das ist nur für ganze Zahlen. Wenn Sie bei einer Art realer Darstellung von Zahlen (log, sqrt, exp usw.) in kompliziertere Funktionen geraten, werden die Dinge noch komplizierter.

Wenn Sie einen theoretischen Hintergrund wünschen, empfehle ich dringend, das erste Kapitel von Yaps Buch "Grundlegende Probleme der algorithmischen Algebra" zu lesen . Wie bereits erwähnt, ist die gmp bignum Bibliothek eine ausgezeichnete Bibliothek. Für reelle Zahlen habe ich mpfr verwendet und es hat mir gefallen.

Erfinden Sie das Rad nicht neu: Es könnte sich als quadratisch herausstellen!

Verwenden Sie eine bewährte Bibliothek eines Drittanbieters wie GNU MP .

Sie machen es im Grunde genauso wie mit Bleistift und Papier ...

• Die Zahl soll in einem Puffer (Array) dargestellt werden, der nach Bedarf eine beliebige Größe annehmen kann (dh mit mallocund realloc)
• Sie implementieren grundlegende Arithmetik so weit wie möglich mithilfe sprachgestützter Strukturen und behandeln das Übertragen und Verschieben des Radixpunkts manuell
• Sie durchsuchen numerische Analysetexte, um effiziente Argumente für den Umgang mit komplexeren Funktionen zu finden
• Sie implementieren nur so viel, wie Sie benötigen.

In der Regel verwenden Sie als grundlegende Berechnungseinheit

• Bytes mit 0-99 oder 0-255
• 16-Bit-Wörter mit 0-9999 oder 0-65536
• 32-Bit-Wörter mit ...
• ...

wie von Ihrer Architektur vorgegeben.

Die Wahl der binären oder dezimalen Basis hängt von Ihren Wünschen nach maximaler Raumeffizienz, menschlicher Lesbarkeit und dem Fehlen von BCD-Mathematikunterstützung (Binary Coded Decimal) auf Ihrem Chip ab.

Sie können es mit High-School-Niveau der Mathematik tun. In der Realität werden jedoch fortgeschrittenere Algorithmen verwendet. So fügen Sie beispielsweise zwei 1024-Byte-Zahlen hinzu:

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;
}

Das Ergebnis muss one placeim Falle einer Addition größer sein , um die Maximalwerte zu berücksichtigen. Schau dir das an :

9
   +
9
----
18

TTMath ist eine großartige Bibliothek, wenn Sie lernen möchten. Es wird mit C ++ erstellt. Das obige Beispiel war albern, aber so erfolgt das Addieren und Subtrahieren im Allgemeinen!

Eine gute Referenz zu diesem Thema ist die rechnerische Komplexität mathematischer Operationen . Hier erfahren Sie, wie viel Speicherplatz für jede Operation erforderlich ist, die Sie implementieren möchten. Wenn Sie beispielsweise zwei N-digitZahlen haben, müssen Sie 2N digitsdas Ergebnis der Multiplikation speichern.

Wie Mitch sagte, ist es bei weitem keine leichte Aufgabe, sie umzusetzen! Ich empfehle Ihnen, sich TTMath anzuschauen, wenn Sie C ++ kennen.

Eine der ultimativen Referenzen (IMHO) ist Knuths TAOCP Volume II. Es werden viele Algorithmen zur Darstellung von Zahlen und arithmetischen Operationen für diese Darstellungen erläutert.

@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},
}

Angenommen, Sie möchten selbst einen großen Ganzzahlcode schreiben, kann dies überraschend einfach sein und als jemand gesprochen werden, der dies kürzlich getan hat (allerdings in MATLAB). Hier sind einige der Tricks, die ich verwendet habe:

• Ich habe jede einzelne Dezimalstelle als doppelte Zahl gespeichert. Dies macht viele Operationen einfach, insbesondere die Ausgabe. Obwohl es mehr Speicherplatz beansprucht, als Sie vielleicht wünschen, ist Speicher hier billig und macht die Multiplikation sehr effizient, wenn Sie ein Vektorpaar effizient falten können. Alternativ können Sie mehrere Dezimalstellen doppelt speichern. Beachten Sie jedoch, dass die Faltung zur Multiplikation bei sehr großen Zahlen zu numerischen Problemen führen kann.

• Speichern Sie ein Vorzeichenbit separat.

• Das Hinzufügen von zwei Zahlen besteht hauptsächlich darin, die Ziffern zu addieren und dann bei jedem Schritt auf einen Übertrag zu prüfen.

• Die Multiplikation eines Zahlenpaars erfolgt am besten als Faltung, gefolgt von einem Übertragsschritt, zumindest wenn Sie einen schnellen Faltungscode haben.

• Selbst wenn Sie die Zahlen als Folge von einzelnen Dezimalstellen speichern, können Sie durch Teilen (auch Mod / Rem ops) ungefähr 13 Dezimalstellen gleichzeitig im Ergebnis erhalten. Dies ist viel effizienter als eine Division, die jeweils nur mit einer Dezimalstelle arbeitet.

• Um eine ganzzahlige Potenz einer ganzen Zahl zu berechnen, berechnen Sie die binäre Darstellung des Exponenten. Verwenden Sie dann wiederholte Quadrierungsoperationen, um die Potenzen nach Bedarf zu berechnen.

• Viele Operationen (Factoring, Primalitätstests usw.) profitieren von einer Powermod-Operation. Das heißt, wenn Sie mod (a ^ p, N) berechnen, reduzieren Sie das Ergebnis mod N bei jedem Schritt der Potenzierung, bei dem p in einer binären Form ausgedrückt wurde. Berechnen Sie nicht zuerst a ^ p und versuchen Sie dann, es mod N zu reduzieren.

Hier ist ein einfaches (naives) Beispiel, das ich in PHP gemacht habe.

Ich habe "Hinzufügen" und "Multiplizieren" implementiert und dies für ein Exponentenbeispiel verwendet.

http://adevsoft.com/simple-php-arbitrary-precision-integer-big-num-example/

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);
}