Langzahlarithmetik

Beteilige dich an der Diskussion!

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)

Die Langzahlarithmetik beschäftigt sich mit dem Rechnen mit Zahlen, bei denen eine sehr hohe Anzahl an Stellen zu verarbeiten ist.

Ein Computer hat eingebaute Befehle, um mit kleinen Zahlen extrem schnell zu rechnen. Der Zahlenbereich dieser „kleinen“ Zahlen umfasst üblicherweise ±2 Milliarden (bei 32-Bit-Computern) oder ±9 Trillionen (bei 64-Bit-Computern). Alles, was darüber hinausgeht, kann der Computer nicht mehr von sich aus berechnen, sondern braucht speziell zu diesem Zweck geschriebene Programme, die die Rechenregeln für große Zahlen definieren.

Die meisten Computer können nicht nur mit ganzen Zahlen rechnen, sondern haben auch eingebaute Befehle für Gleitkommazahlen. Das sind Zahlen, die aus einer festen Anzahl an Ziffern bestehen, bei denen das Komma jedoch an beliebiger Stelle sitzen kann. Üblicherweise haben Gleitkommazahlen 16 Stellen Genauigkeit. Auch hier gibt es Anwendungen, die exakter rechnen müssen, so dass die eingebauten Rechenbefehle nicht ausreichen.

Anwendungen

Die Berechnung der Kreiszahl anhand der Srinivasa-Ramanujan-Formel ergibt nach 9 Iterationen einen Näherungsbruch mit 80-stelligem Zähler

Anwendungen der Langzahlarithmetik sind z. B.:

• Wenn mit großen Zahlen exakt gerechnet werden muss, etwa in der Kryptographie oder bei vielen Anwendungen von Fakultäten und Binomialkoeffizienten;
• Wenn Zahlen wie Pi oder andere mathematische Konstanten auf möglichst viele Stellen genau ermittelt werden sollen, wobei Näherungsbrüche mit vielstelligen Zählern und Nennern in Dezimalzahlen umzurechnen sind;
• Wenn man Systeme simuliert, deren Verhalten so empfindlich von den Anfangsbedingungen abhängt (sog. Schmetterlingseffekt), dass die begrenzte Genauigkeit gewöhnlicher Arithmetik das Ergebnis unbrauchbar macht;
• Wenn Programmiersprachen implementiert werden, die das Überlaufen von Variablen automatisch tolerieren können.

Umsetzung

Um mit langen Zahlen zu rechnen, benutzen Computer sehr verschiedene Verfahren, abhängig von der Art der Operation und der Operanden. Mit dezimalen Ziffern wird in der heutigen Zeit nie gerechnet. Umrechnung in Dezimalziffern erfolgt nur, wenn diese benötigt werden.

Addition und Subtraktion

4-Bit Addierer, aufgebaut aus Volladdern

Klassische CPUs weisen Befehle für Ganzzahl-Addition und -Subtraktion mit Übertrag auf. Diese Fähigkeit sind normale Eigenschaften von Multibit-Addierern und fallen nebenbei mit ab, siehe Zeichnung rechts. Die heißen üblicherweise ADC oder ADCS bzw. SBC, SBB oder SUBCS. 8-Bit-Computer benötigten diese, um 16-Bit- und 32-Bit-Zahlen oder gar Gleitkommazahlen zu addieren. Es handelt sich dabei um eine schriftliche Addition bzw. schriftlichen Subtraktion zur Basis 2⁴, 2⁸, 2¹⁶, 2³² oder 2⁶⁴, je nach Bitbreite der CPU bei Rechnungen im Binärsystem.

Die verwendete Operation einer 4-Bit-CPU lautet als Pseudocode

(C4, S3...0) = (A3...0) + (B3...0) + C0  oder anders aufgeschrieben

(S4, S3...0) = (A3...0) + (B3...0) + S4'

bzw. allgemeiner:

(CN, SN−1...0) = (AN−1...0) + (BN−1...0) + C0  oder anders aufgeschrieben

(SN, SN−1...0) = (AN−1...0) + (BN−1...0) + SN'

ADC S, A, B, wobei die Funktion SN bzw. SN' vom Übertragsflag im Statusregister übernommen wird.

Der Pseudo-Code lautet dann:

    int N;                               // S[N-1...0] = A[N-1...0] + B[N-1...0]
    int c = 0;                           // Carry-Flag
    T   A[N], B[N], S[N];
    for (int i = 0; i < N; i++)          // beginnend vom niedrigwertigen Teil
        (c, S[i]) = ADC (A[i], B[i], c); // z.B. 33 bit = 32 bit + 32 bit + 1 bit

Überläufe sowie Spezialbehandlung von sehr unterschiedlich langen Zahlen werden hier erst mal nicht behandelt.

Multiplikation mit kleiner Ganzzahl

Multiplikationen erfolgen mit dem Befehl

(C2N−1...N, PN−1...0) = (AN−1...0) × (BN−1...0) + CN−1...0  oder anders aufgeschrieben

(S2N−1...N, PN−1...0) = (AN−1...0) × (BN−1...0) + S2N−1...N'

MUL S, A, B, wobei die Funktion S2N−1...N bzw. S2N−1...N' vom einem weiteren Register übernommen wird.

Der Pseudo-Code lautet dann:

    int N;                                  // P[N-1...0] = A[N-1...0] × Q
    T   c = 0;                              // Carry-Flag
    T   A[], B, P[];
    for (int i = 0; i < N; i++)             // beginnend vom niedrigwertigen Teil
        (c, P[i]) = MULADD (A[i], B, c);    // z.B. 64 bit = 32 bit × 32 bit + 32 bit

Für vorzeichenbehaftete Zahlen sind ggf. Nachbehandlungen notwendig.

Division mit kleiner Ganzzahl

Divisionen erfolgen mit dem Befehl

(R2N−1...N, QN−1...0) = (A2N−1...N, AN−1...0) / (BN−1...0)

Der Pseudo-Code lautet dann:

    int N;                                         // Q[N-1...0] = A[N-1...0] / B
    T   c = 0;                                     // Carry-Flag
    T   A[], B, Q[];
    for (int i = N-1; i >= 0; i--)                 // beginnend vom niedrigwertigen Teil
        (c, Q[i]) = DIVREM (c, A[i], B);           // z.B. 64 bit / 32 bit = 32 bit, Rest 32 bit

Allgemeine Multiplikation

Bei der Multiplikation gibt es bereits verschiedenste Ansätze für Algorithmen, wie zum Beispiel den Karazuba-Algorithmus oder den Schönhage-Strassen-Algorithmus. Es gibt die Vermutung, dass die Schranke $O(n\cdot \log(n))$ bei der Komplexität nicht unterboten werden kann.

Sie zerlegen große Zahlen in ihre Ziffern, rechnen dann die Teilergebnisse aus und setzen die Teilergebnisse dann zum Endergebnis zusammen. Der einzige Unterschied ist, dass Menschen üblicherweise mit den 10 Ziffern von 0 bis 9 rechnen, Computer jedoch mit größeren „Ziffern“ von 0 bis 2 Milliarden, 9 Trillionen oder gar 170 Quintilliarden, da sie für diese Zifferngrößen bereits eingebaute Befehle haben.

In der Langzahlarithmetik setzt nun nicht die Prozessorarchitektur, sondern die Größe des verfügbaren Arbeitsspeichers den Spielraum, innerhalb dessen beliebig lange Zahlen verarbeitet werden können. Bei einigen modernen Programmiersprachen ist Langzahlarithmetik standardmäßig eingebaut, bei anderen stehen dafür Bibliotheken zur Verfügung. Computeralgebrasysteme unterstützen (neben der symbolischen Mathematik, mit der sie nicht zu verwechseln ist) seit jeher auch Langzahlarithmetik.

Bei der Implementierung stehen möglichst effiziente mathematische Algorithmen im Vordergrund, um die Berechnungszeiten zu minimieren.

Programmiersprachen

Programmiersprachen, die Langzahlarithmetik unterstützen, entweder als eingebaute Funktionalität oder im Rahmen der Standardbibliothek:

• Common Lisp: Der ANSI Common Lisp Standard unterstützt Langzahlarithmetik (ganze, rationale und komplexe Zahlen).
• C#: System.Numerics.BigInteger, aus .NET Framework 4.0
• ColdFusion: die vordefinierte Funktion PrecisionEvaluate() berechnet einen oder mehrere string-Ausdrücke dynamisch von links nach rechts mit Dezimalarithmetik.
• D: Standardbibliothek std.bigint
• Dart: Der eingebaute Datentyp int unterstützt Langzahlarithmetik.
• Erlang: Der eingebaute Datentyp Integer unterstützt Langzahlarithmetik.
• Go: Die Standardbibliothek big unterstützt Langzahlarithmetik für Ganzzahlen (Typ Int) und rationale Zahlen (Typ Rat).
• Haskell: Der eingebaute Datentyp Integer unterstützt Langzahlarithmetik und das Standardmodul Data.Ratio unterstützt rationale Zahlen.
• Icon: Unterstützt LIA (Large Integer Arithmetik), wodurch z. B. Wurzeln, Fakultäten, Binomialkoeffizienten u. ä. mit beliebig vielen Stellen berechnet werden können.
• ISLISP: Der ISO/IEC 13816:1997(E) ISLISP Standard unterstützt Langzahlarithmetik für Ganzzahlen.
• J: Eingebaute extended precision
• Java: class java.math.BigInteger (Ganzzahlen), class java.math.BigDecimal (Dezimalbrüche)
• JavaScript: Der eingebaute Datentyp BigInt unterstützt Langzahlarithmetik. Für ältere Versionen: Die Bibliothek gwt-math definiert ein Interface für java.math.BigDecimal, und die Bibliothek BigInt unterstützt Langzahlarithmetik für ganze Zahlen.
• OCaml: Die Bibliothek Num unterstützt Langzahlarithmetik für ganze und rationale Zahlen.
• Perl: Die Pragmas bignum und bigrat ermöglichen BigNum und BigRational Unterstützung für Perl.
• PHP: Das Modul BC Math unterstützt Langzahlarithmetik.
• Pike: Der eingebaute Typ int wechselt automatisch von maschinennaher Darstellung von Ganzzahlen auf Langzahlarithmetik, sobald ein Wert nicht in maschinennaher Darstellung dargestellt werden kann.
• Python: Der eingebaute Typ int (3.x) / long (2.x) unterstützt Langzahlarithmetik. Die Klasse Decimal der Standardbibliothek decimal hat benutzerdefinierbare Genauigkeit und einige mathematischen Funktionen (Exponentialfunktion, Quadratwurzel etc. aber keine trigonometrischen Funktionen). Mehr Langzahlarithmetik für Gleitkommazahlen ist mit den Bibliotheken „mpmath“ und „bigfloat“ von Drittanbietern ermöglicht.
• Racket: Die eingebauten exact Zahlen benutzen Langzahlarithmetik für ganze und rationale Zahlen.
• REXX: Varianten inklusive Open Object Rexx und NetRexx
• Ruby: Der eingebaute Ganzzahltyp Bignum unterstützt Langzahlarithmetik. Die Klasse BigDecimal aus der Standardbibliothek bigdecimal unterstützt Langzahlarithmetik auf Dezimalbrüchen.
• Scheme: R⁵RS erlaubt, und R⁶RS verlangt, dass ganze und rationale Zahlen Langzahlarithmetik unterstützen.
• Scala: Class BigInt und Class BigDecimal.
• Seed7: bigInteger und bigRational.
• Smalltalk: Varianten einschließlich Squeak, Smalltalk/X, GNU Smalltalk, Dolphin Smalltalk etc.
• Standard ML: Die optional eingebaute Struktur IntInf implementiert INTEGER und unterstützt Langzahlarithmetik für Ganzzahlen.
• TeX (Textsatzsystem): Erweiterungspakete bigintcalc und xint.