Langzahlarithmetik

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 die gleichen Verfahren wie bei der schriftlichen Addition und der schriftlichen Subtraktion. 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.

Addition und Subtraktion

Wenn n die Wortbreite des Prozessors ist, dann werden zur Addition von langen Zahlen die Summanden mit den niederwertigsten Wortes (Bits 0 bis n-1) beginnend addiert. Ein dabei auftretender Übertrag wird im Carry-Bit des Prozessors gespeichert und in die Addition des nächst-höherwertigen Wortes (Bits n bis 2n-1) eingebracht. So wird fortgefahren, bis alle Worte verarbeitet sind.

Die Subtraktion erfolgt analog dazu. Im Fall eines negativen Ergebnisses verbleibt das Carry-Bit nach Abschluss der Operation gesetzt und man erhält eine Darstellung der Differenz im Zweier-Komplement.

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.

Programmiersprachen

Programmiersprachen, die Langzahlenarithmetik 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 (integer), class java.math.BigDecimal (decimal)
• 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. Z.B.: (expt 10 100) erzeugt das erwartete (große) Ergebnis. Exacte Zahlen unterstützen auch rationale Zahlen, so produziert (/ 3 4) 3/4.
• 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.
• 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.

Selbständige Programme

• ARIBAS gibt beispielsweise exakte Fakultäten aus und vollführt (weniger exakte) Primzahltests unter UNIX, Linux, MS-DOS, MS Windows sowie auf dem Atari ST.