Langzahlarithmetik

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
QS-Informatik
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 verschoben werden 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[Bearbeiten | Quelltext bearbeiten]

Anwendungen der Langzahlarithmetik sind z. B.:

Umsetzung[Bearbeiten | Quelltext bearbeiten]

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[Bearbeiten | Quelltext bearbeiten]

Bei Addition und Subtraktion von langen Zahlen werden die einzelnen binären Ziffernblöcke getrennt addiert bzw. subtrahiert und ein Übertragsbit übergeben.

Multiplikation[Bearbeiten | Quelltext bearbeiten]

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 bei der Komplexität nicht unterboten werden kann.

Programmiersprachen[Bearbeiten | Quelltext bearbeiten]

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: 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: R5RS erlaubt, und R6RS 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[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. Otto Forster: ARIBAS by O. Forster. Mathematische Fakultät der Ludwig-Maximilians-Universität München, 26. Januar 2010, abgerufen am 31. Mai 2018.