Langzahlarithmetik

Grundidee und Bedeutung

Langzahlarithmetik beschäftigt sich mit dem Rechnen mit Zahlen, bei denen eine sehr hohe Anzahl an Stellen zu verarbeiten ist. Eingebaute Computerbefehle arbeiten nur innerhalb eines begrenzten Zahlenbereichs: Üblicherweise reicht er bei 32-Bit-Computern von etwa −2 Milliarden bis +2 Milliarden und bei 64-Bit-Computern von etwa −9 Trillionen bis +9 Trillionen. Zahlen außerhalb dieses Bereichs erfordern speziell entwickelte Programme, die die Rechenregeln für große Zahlen festlegen.

Auch Gleitkommazahlen, also Zahlen mit einer festen Anzahl an Ziffern und einem beliebig verschiebbaren Komma, sind in ihrer Genauigkeit begrenzt. Üblicherweise bieten sie 16 Stellen Genauigkeit. Für Anwendungen, die exakter rechnen müssen, reichen die eingebauten Befehle daher ebenfalls nicht aus.

Bei der Langzahlarithmetik begrenzt nicht mehr die Prozessorarchitektur, sondern hauptsächlich die Größe des verfügbaren Arbeitsspeichers, wie lange Zahlen verarbeitet werden können. Dezimale Ziffern werden dabei in der heutigen Zeit nicht direkt verwendet; in Dezimalziffern wird erst umgerechnet, wenn dies benötigt wird.

Typische Anwendungen

Langzahlarithmetik wird eingesetzt, wenn große Zahlen exakt oder mit besonders hoher Genauigkeit verarbeitet werden müssen. Wichtige Beispiele sind:

• Kryptographie sowie Berechnungen mit Fakultäten und Binomialkoeffizienten, bei denen große Ganzzahlen exakt gebraucht werden.
• Die Berechnung von π und anderen mathematischen Konstanten auf möglichst viele Stellen. Dabei müssen Näherungsbrüche mit vielstelligen Zählern und Nennern in Dezimalzahlen umgerechnet werden.
• Simulationen empfindlicher Systeme. Beim sogenannten Schmetterlingseffekt können kleine Abweichungen der Anfangsbedingungen das Ergebnis stark verändern, sodass die begrenzte Genauigkeit gewöhnlicher Arithmetik unbrauchbar wird.
• Programmiersprachen, die das Überlaufen von Variablen automatisch tolerieren können.

Als Beispiel nennt der Artikel die Berechnung der Kreiszahl mit der Srinivasa-Ramanujan-Formel: Nach 9 Iterationen entsteht ein Näherungsbruch mit einem 80-stelligen Zähler.

Addition und Subtraktion

Große Zahlen werden in mehrere Teilstücke zerlegt und wie bei einer schriftlichen Addition oder Subtraktion verarbeitet. Klassische CPUs besitzen Ganzzahlbefehle mit Übertrag, die meist ADC oder ADCS für die Addition sowie SBC, SBB oder SUBCS für die Subtraktion heißen. Diese Befehle sind normale Eigenschaften von Multibit-Addierern.

Je nach Bitbreite der CPU wird dabei zur Basis 2^4, 2^8, 2^16, 2^32 oder 2^64 gerechnet. Ein 8-Bit-Computer kann so beispielsweise 16-Bit- und 32-Bit-Zahlen oder Gleitkommazahlen in mehreren Schritten addieren.

Für eine 4-Bit-CPU lautet die Grundidee: (C₄, S₃…₀) = (A₃…₀) + (B₃…₀) + C₀. Allgemein gilt: (C_N, S_{N−1…0}) = (A_{N−1…0}) + (B_{N−1…0}) + C₀. Dabei ist C das Übertragsbit, S das Ergebnis und A sowie B sind die Operanden. Der Übertrag kann aus dem Carry- beziehungsweise Übertragsflag des Statusregisters übernommen werden.

Der Pseudocode verarbeitet die Teilstücke vom niedrigwertigen zum höchstwertigen Teil: int c = 0; for (int i = 0; i < N; i++) (c, S[i]) = ADC(A[i], B[i], c);

Damit kann zum Beispiel eine 32-Bit-Zahl mit einer anderen 32-Bit-Zahl und einem zusätzlichen 1-Bit-Übertrag verarbeitet werden. Überläufe und die Sonderbehandlung unterschiedlich langer Zahlen werden in diesem einfachen Verfahren noch nicht behandelt.

Multiplikation und Division mit kleiner Ganzzahl

Für die Multiplikation eines langen Operanden mit einer kleineren Ganzzahl wird ein MUL- beziehungsweise MULADD-Befehl verwendet. Das Produkt wird in einen unteren Ergebnisanteil P und einen oberen Übertragsanteil C zerlegt: (C_{2N−1…N}, P_{N−1…0}) = (A_{N−1…0}) × (B_{N−1…0}) + C_{N−1…0}.

Der Pseudocode beginnt beim niedrigwertigen Teil und übernimmt den Übertrag in den nächsten Schritt: int c = 0; for (int i = 0; i < N; i++) (c, P[i]) = MULADD(A[i], B, c);

Das Beispiel im Artikel beschreibt eine Rechnung von 32 bit × 32 bit + 32 bit mit einem 64-Bit-Ergebnis. Bei vorzeichenbehafteten Zahlen können Nachbehandlungen erforderlich sein.

Bei der Division wird der lange Dividend durch eine kleinere Ganzzahl geteilt. Das Ergebnis ist der Quotient Q; zusätzlich entsteht ein Rest R: (R_{2N−1…N}, Q_{N−1…0}) = (A_{2N−1…N}, A_{N−1…0}) / (B_{N−1…0}).

Der Pseudocode durchläuft die Teilstücke in der angegebenen Reihenfolge und verwendet DIVREM: int c = 0; for (int i = N−1; i >= 0; i--) (c, Q[i]) = DIVREM(c, A[i], B);

Als Beispiel nennt der Artikel: 64 bit / 32 bit = 32 bit Quotient und 32 bit Rest.

Allgemeine Multiplikation

Bei der Multiplikation zweier langer Zahlen gibt es verschiedene Algorithmen, darunter den Karazuba-Algorithmus und den Schönhage-Strassen-Algorithmus. Im Artikel wird die Vermutung genannt, dass die Schranke O(n · log(n)) für die Komplexität nicht unterboten werden kann.

Das Grundprinzip ähnelt der schriftlichen Multiplikation: Große Zahlen werden in Teilziffern zerlegt, die Teilergebnisse werden berechnet und anschließend zum Endergebnis zusammengesetzt. Menschen verwenden dabei üblicherweise die 10 Ziffern von 0 bis 9. Computer arbeiten dagegen mit größeren „Ziffern“, beispielsweise mit Werten bis 2 Milliarden, 9 Trillionen oder sogar 170 Quintilliarden, weil dafür bereits eingebaute Rechenbefehle vorhanden sind.

Bei der Implementierung stehen effiziente mathematische Algorithmen im Vordergrund, um die Berechnungszeit möglichst gering zu halten. Moderne Programmiersprachen bieten Langzahlarithmetik teilweise standardmäßig an; ansonsten stehen Bibliotheken zur Verfügung. Computeralgebrasysteme unterstützen sie neben der symbolischen Mathematik ebenfalls seit jeher.

Unterstützung in Programmiersprachen

Langzahlarithmetik ist in vielen Programmiersprachen entweder eingebaut oder über die Standardbibliothek beziehungsweise Zusatzbibliotheken verfügbar. Der Artikel nennt unter anderem:

• Common Lisp unterstützt ganze, rationale und komplexe Zahlen.
• C# stellt System.Numerics.BigInteger ab .NET Framework 4.0 bereit.
• D verwendet std.bigint; Go bietet big für ganze Zahlen (Int) und rationale Zahlen (Rat).
• Dart, Erlang und Python unterstützen Langzahlarithmetik über eingebaute Ganzzahltypen. In Python gilt dies für int in 3.x beziehungsweise long in 2.x. Decimal erlaubt benutzerdefinierbare Genauigkeit; für Gleitkommazahlen werden außerdem mpmath und bigfloat genannt.
• Haskell verwendet Integer und Data.Ratio, Java BigInteger und BigDecimal. JavaScript besitzt den eingebauten Datentyp BigInt.
• OCaml bietet die Bibliothek Num, PHP das Modul BC Math, Perl die Pragmas bignum und bigrat und Ruby die Typen Bignum und BigDecimal.
• Racket, REXX, Scheme, Scala, Seed7, Smalltalk und Standard ML unterstützen Langzahlarithmetik in eingebauten Typen, Strukturen oder Varianten. Für Scheme wird genannt, dass R^5RS sie erlaubt und R^6RS sie verlangt.
• Weitere im Artikel aufgeführte Möglichkeiten sind Icon mit LIA (Large Integer Arithmetik), ISLISP nach ISO/IEC 13816:1997(E), J mit extended precision sowie TeX über bigintcalc und xint.

Je nach Sprache betrifft die Unterstützung nur Ganzzahlen oder zusätzlich rationale Zahlen und Dezimalbrüche. Funktionen für beliebig genaue Gleitkommazahlen sind teilweise nur über spezielle Bibliotheken verfügbar.