Langzahlarithmetik

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
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.

In der herkömmlichen Computerarithmetik begrenzt die Länge des Datenworts, das im Rechenwerk des Prozessors Platz findet, die Länge der Zahlen, mit denen gerechnet werden kann. In heutigen Rechnern sind das typischerweise 32 oder 64 Bit. Diese Hardwareeigenschaft spiegelt sich wider in dem Sortiment an elementaren numerischen Datentypen, die die Programmiersprachen zur Verfügung stellen, und die maximal Raum bieten für vorzeichenbehaftete Ganzzahlen von −2.147.483.648 bis 2.147.483.647, bzw., bei 64-Bit-Rechnern, von −9.223.372.036.854.775.808 bis 9.223.372.036.854.775.807.[1] Bei Gleitkommavariablen spielt zumeist die Begrenzung der Genauigkeit, weniger der Wertebereich, eine Rolle.

Anwendungen[Bearbeiten]

Anwendungen der Langzahlarithmetik sind z.B.:

Umsetzung[Bearbeiten]

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.

Eine sehr häufig angewandte Methode beim Rechnen mit großen Zahlen ist die Hintereinanderausführung einzelner Rechenschritte mit kleineren Zahlen. So kann man beispielsweise die Ziffern einer 1024-stelligen Binärzahl auf sechzehn 64-stellige Binärzahlen aufteilen und damit auf einem kleineren Prozessor rechnen.

Addition und Subtraktion[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]

Bei der Multiplikation gibt es bereits verschiedenste Ansätze für Algorithmen, wie zum Beispiel den Karatsuba-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[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.
  • 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 inclusive 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.

Einzelnachweise[Bearbeiten]

  1. Integer_(Datentyp)#Maximaler_Wertebereich_von_Integer