Arbiträr-arithmetische Erklärung

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. Mir ist bewusst, dass es Bibliotheken dafür gibt, aber ich möchte versuchen, es selbst zu implementieren.

Ich will nur wissen, ob irgendjemand eine sehr detaillierte, dumpfe Erklärung der Arithmetik mit willkürlicher Genauigkeit hat oder liefern kann.

Solutions Collecting From Web of "Arbiträr-arithmetische Erklärung"

Es sind alles angemessene Speicher und Algorithmen, um Zahlen als kleinere Teile zu behandeln. Nehmen wir an, Sie haben einen Compiler, in dem ein int nur 0 bis 99 sein kann und Sie Zahlen bis zu 999999 behandeln wollen (wir werden uns nur um positive Zahlen kümmern, um es einfach zu halten).

Sie tun das, indem Sie jeder Zahl drei int s geben und die gleichen Regeln int , die Sie in der Grundschule für Addition, Subtraktion und die anderen Grundoperationen gelernt haben (müssen).

In einer Bibliothek mit beliebiger Genauigkeit gibt es kein festes Limit für die Anzahl der Basistypen, die zur Darstellung unserer Zahlen verwendet werden.

Zusatz zum Beispiel: 123456 + 78 :

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

Arbeiten vom am wenigsten signifikanten Ende:

  • Anfangsü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

Dies ist in der Tat, wie Addition in der Regel auf der Bit-Ebene in Ihrer CPU funktioniert.

Subtraktion ist ähnlich (Subtraktion des Basistyps und Borrow statt Carry), Multiplikation kann mit wiederholten Additionen (sehr langsam) oder Kreuzprodukten (schneller) durchgeführt werden und die Division ist schwieriger, kann aber durch Verschieben und Subtraktion der Zahlen erfolgen beteiligt (die lange Teilung, die du als Kind gelernt hättest).

Ich habe tatsächlich Bibliotheken geschrieben, um diese Art von Sachen mit den maximalen Zehnerpotenzen zu machen, die in eine ganze Zahl passen, wenn sie quadriert werden (um einen Überlauf zu vermeiden, wenn zwei int s multipliziert werden, wie ein 16-bit int , der auf 0 begrenzt ist) 99, um 9.801 (<32.768) im Quadrat zu erzeugen, oder 32-Bit- int Verwendung von 0 bis 9.999, um 99.980.001 (<2.147.483.648) zu erzeugen, was die Algorithmen erheblich erleichterte.

Einige Tricks, auf die man achten sollte.

1 / Wenn du Zahlen addierst oder multiplizierst, reserviere den maximalen Speicherplatz, den du benötigst, und verringere sie später, wenn du findest, dass es zu viel ist. Wenn Sie beispielsweise zwei 100- “Ziffern” (wobei Ziffer eine Zahl ist) Zahlen hinzufügen, erhalten Sie nie mehr als 101 Ziffern. Wenn Sie eine 12-stellige Zahl mit einer 3-stelligen Zahl multiplizieren, werden niemals mehr als 15 Ziffern generiert (addieren Sie die Ziffernanzahl).

2 / Für zusätzliche Geschwindigkeit, normalisieren (reduzieren Sie den Speicher erforderlich), die Zahlen nur wenn absolut notwendig – meine Bibliothek hatte dies als ein separates Gespräch, so dass der Benutzer zwischen Geschwindigkeit und Speicher Bedenken entscheiden kann.

3 / Addition einer positiven und negativen Zahl ist Subtraktion, und Subtraktion einer negativen Zahl ist die gleiche wie das Hinzufügen der äquivalenten positiven. Sie können eine Menge Code sparen, indem Sie die Add- und Subtract-Methoden nach dem Anpassen der Zeichen aufrufen.

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

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

Ziehe stattdessen 10 von 11 ab und negiere es dann:

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

Hier sind die Kommentare (in Text umgewandelt) von einer der Bibliotheken, für die ich das tun musste. Der Code selbst ist leider urheberrechtlich geschützt, aber Sie können möglicherweise genügend Informationen auswählen, um die vier Grundoperationen zu bewältigen. Nehmen wir an, dass -a und -b negative Zahlen darstellen und a und b Null- oder positive Zahlen sind.

Wenn die Zeichen anders sind, verwenden Sie die Subtraktion der Negation:

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

Verwenden Sie für die Subtraktion , wenn die Zeichen unterschiedlich sind, die Addition der Negation:

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

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

 small - big becomes -(big - small) 

Multiplikation verwendet Mathe auf Einstiegsebene wie folgt:

 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 nacheinander (rückwärts) zu extrahieren und dann mit add einen Wert zu berechnen, der zu dem Ergebnis addiert wird (anfänglich Null).

ShiftLeft und ShiftRight Operationen werden verwendet, um LongInt schnell mit dem ShiftRight zu multiplizieren oder zu dividieren (10 für “echte” Mathematik). Im obigen Beispiel addieren wir 475 zu Null 2 ​​Mal (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 zu Null, um 14250 zu erhalten, dann addiere zum Ergebnis von 950, um 15200 zu erhalten.

Left Shift 4750, um 47500 zu erhalten, Right Shift 3, um 0 zu erhalten. Da die nach rechts verschobene 32 nun Null ist, sind wir fertig und tatsächlich sind 475 x 32 gleich 15200.

Die Division ist auch schwierig, basiert aber auf früher Arithmetik (die “gazinta” -Methode für “geht in”). Betrachten Sie die folgende lange Division 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 ist 12345 / 27 457 mit Rest 6 . Überprüfen:

  457 x 27 + 6 = 12339 + 6 = 12345 

Dies wird implementiert, indem eine Draw-Down-Variable (anfänglich Null) verwendet wird, um die Segmente von 12345 nacheinander zu verkleinern, bis sie größer oder gleich 27 ist.

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

Wenn keine Segmente mehr zu Fall bringen, haben wir unser Ergebnis.


Beachten Sie, dass dies ziemlich grundlegende Algorithmen sind. Es gibt viel bessere Möglichkeiten, komplexe Berechnungen durchzuführen, wenn Ihre Zahlen besonders groß sind. Sie können in etwas wie GNU Multiple Precision Arithmetic Library schauen – es ist wesentlich besser und schneller als meine eigenen Bibliotheken.

Es hat das ziemlich unglückliche Fehlverhalten darin, dass es einfach beendet wird, wenn es nicht genügend Speicher hat (ein ziemlich fataler Fehler für eine allgemeine Bibliothek meiner Meinung nach), aber, wenn Sie darüber hinausschauen 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 einfach ohne ersichtlichen Grund beendet wird), könnten Sie zumindest die Algorithmen von dort erhalten, um sie in Ihren eigenen Code zu integrieren.

Ich habe auch festgestellt, dass die bods bei MPIR (eine Abzweigung von GMP) zugänglicher für Diskussionen über mögliche Änderungen sind – sie scheinen ein entwicklerfreundlicherer Haufen zu sein.

Während das Rad neu erfinden ist sehr gut für Ihre persönliche Erbauung und Lernen, es ist auch eine sehr große Aufgabe. Ich möchte Sie nicht davon abhalten, dass es eine wichtige Übung ist und eine, die ich selbst gemacht habe, aber Sie sollten wissen, dass es subtile und komplexe Probleme bei der Arbeit gibt, die bei größeren Paketen angesprochen werden.

Zum Beispiel Multiplikation. Naiv, denken Sie vielleicht an die “Schuljungen” -Methode, dh schreiben Sie eine Zahl über die andere, dann machen Sie lange Multiplikation, wie Sie in der Schule gelernt haben. Beispiel:

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

aber diese Methode ist extrem langsam (O (n ^ 2), wobei n die Anzahl der Ziffern 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 in kompliziertere functionen auf irgendeine Art von reeller Darstellung der Zahl (log, sqrt, exp usw.) kommen, werden die Dinge noch komplizierter.

Wenn Sie einen theoretischen Hintergrund wünschen, empfehle ich Ihnen, das erste Kapitel von Yaps Buch “Fundamental Problems of Algorithmic Algebra” zu lesen. Wie bereits erwähnt, ist die gmp bignum-Bibliothek eine ausgezeichnete Bibliothek. Für echte Zahlen habe ich mpfr verwendet und es gemocht.

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

Verwenden Sie eine bewährte Bibliothek von Drittanbietern wie GNU MP .

Sie machen das im Prinzip genauso wie mit Bleistift und Papier …

  • Die Zahl soll in einem Puffer (Array) dargestellt werden, der je nach Bedarf eine beliebige Größe annehmen kann ( realloc malloc und realloc )
  • Sie implementieren grundlegende Arithmetik so weit wie möglich mit sprachgestützten Strukturen und befassen sich mit Trägern und verschieben den Radix-Punkt manuell
  • Sie durchsuchen numerische Analysetexte, um effiziente Argumente für komplexere functionen zu finden
  • Sie implementieren nur so viel wie Sie brauchen.

Normalerweise werden Sie als Basiseinheit der Berechnung verwendet

  • Bytes, die mit 0-99 oder 0-255 enthalten
  • 16-Bit-Wörter, die verwittern, 0-9999 oder 0-65536
  • 32-Bit-Wörter mit …

wie von Ihrer Architektur diktiert.

Die Wahl der binären oder dezimalen Basis hängt von Ihren Wünschen nach maximaler Raumeffizienz, menschlicher Lesbarkeit und dem Fehlen von binär codierter dezimaler (BCD) mathematischer Unterstützung auf Ihrem Chip ab.

Sie können es mit High-School-Niveau der Mathematik tun. Obwohl fortschrittlichere Algorithmen in der Realität verwendet werden. Um zum Beispiel zwei 1024-Byte-Nummern hinzuzufügen:

 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 im Falle einer Addition um one place größer sein, um maximale Werte zu berücksichtigen. Schau dir das an :

 9 + 9 ---- 18 

TTMath ist eine großartige Bibliothek, wenn Sie lernen wollen. Es wird mit C ++ erstellt. Das obige Beispiel war blöd, aber so wird Addition und Subtraktion generell gemacht!

Ein guter Hinweis auf das Thema ist Computational Komplexität von mathematischen Operationen . Es zeigt an, wie viel Speicherplatz für jede Operation benötigt wird, die Sie implementieren möchten. Zum Beispiel, wenn Sie zwei N-digit Zahlen haben, dann benötigen Sie 2N digits , um das Ergebnis der Multiplikation zu speichern.

Wie Mitch sagte, es ist bei weitem keine einfache Aufgabe zu implementieren! Ich empfehle Ihnen, sich TTMath anzusehen, wenn Sie C ++ kennen.

Eine der letzten Referenzen (IMHO) ist Knuths TAOCP Volume II. Es erklärt viele Algorithmen zur Darstellung von Zahlen und arithmetischen Operationen an diesen Darstellungen.

 @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 einen großen Integer-Code selbst schreiben, kann dies überraschend einfach sein, gesprochen als jemand, der es kürzlich getan hat (obwohl in MATLAB.) Hier sind ein paar der Tricks, die ich verwendet habe:

  • Ich habe jede einzelne Dezimalziffer als doppelte Zahl gespeichert. Dies macht viele Operationen einfach, insbesondere die Ausgabe. Obwohl es mehr Speicherplatz benötigt, als Sie vielleicht möchten, ist Speicher hier billig und macht die Multiplikation sehr effizient, wenn Sie ein Paar Vektoren effizient falten können. Alternativ können Sie mehrere Dezimalziffern in einem Double speichern, aber beachten Sie, dass die Faltung zur Multiplikation numerische Probleme bei sehr großen Zahlen verursachen kann.

  • Speichern Sie ein Vorzeichenbit separat.

  • Die Addition von zwei Zahlen ist hauptsächlich eine Frage des Hinzufügens der Ziffern und dann eines Übertrags bei jedem Schritt.

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

  • Selbst wenn Sie die Zahlen als eine Folge von einzelnen Dezimalziffern speichern, kann Division (auch Mod / Rem Ops) durchgeführt werden, um im Ergebnis etwa 13 Dezimalziffern zu erhalten. Dies ist viel effizienter als eine Division, die jeweils nur 1 Dezimalziffer bearbeitet.

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

  • Viele Operationen (Factoring, Primzahltests usw.) profitieren von einem Powermod-Vorgang. Das heißt, wenn Sie mod (a ^ p, N) berechnen, reduzieren Sie das Ergebnis mod N bei jedem Schritt der Potenzierung, wobei p in binärer Form ausgedrückt wurde. Berechne nicht zuerst ein ^ p und versuche dann, es mod N zu reduzieren.

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

Ich habe “Add” und “Multiply” implementiert und das für ein Exponentenbeispiel verwendet.

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

Codeschnipsel

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