Große Nummern

Für manche Berechnungen sind selbst 64 Bit zu wenig. Einige Sprachen können von Haus aus mit größeren Zahlen hantieren; für viele andere gibt es einschlägige Bibliotheken.

In Pocket speichern vorlesen Druckansicht 5 Kommentare lesen
Lesezeit: 5 Min.
Von
  • Michael Riepe

Zehn Jahre ist es her, dass AMD den Opteron mit 64-Bit-Rechenwerk vorstellte. Heute beherrschen nicht nur Server, sondern auch PCs und Notebooks Arithmetik mit 64 Bit. Programme, die mit großen Zahlen hantieren, laufen dadurch um einiges schneller. Für manche Anwendungen sind 64 Bit – umgerechnet 18 Dezimalstellen, 19 bei vorzeichenlosen Zahlen – allerdings immer noch zu wenig. Kryptografische Algorithmen etwa arbeiten mit viel längeren Zahlen.

Einige Berechnungen benötigen zwar nicht mehr als 64 Bit fürs Resultat, es können jedoch Zwischenergebnisse auftreten, die größer sind. Ein klassischer Fall ist die Berechnung des arithmetischen Mittelwerts, bei der man zunächst die Summe aller Einzelwerte ermittelt. Solche Überläufe muss der Programmierer vorhersehen und verhindern – zum Beispiel, indem er für Zwischenergebnisse einen „größeren“ Datentyp verwendet. Soll das Programm für alle Eventualitäten gerüstet sein, empfiehlt sich einer, der bei Bedarf mitwächst.

Solche Zahlentypen findet man in diversen Programmiersprachen. Vorreiter war Lisp mit seinem Datentyp bignum. Die Sprache konvertiert automatisch von integer nach bignum und wieder zurück, was dem Entwickler viel Arbeit abnimmt. Außerdem kennt sie den Datentyp rational für gebrochene Zahlen, dessen Zähler und Nenner wiederum vom Typ integer oder bignum sein dürfen, sodass sich alle rationalen Zahlen ohne Genauigkeitsverlust darstellen lassen – sofern sie ins RAM passen. Seit 2007 verlangt der Scheme-Standard R6RS ebenfalls Unterstützung für diese Datentypen.

Ohne Hilfsmittel mit großen Ganzzahlen rechnen kann man auch in Python oder Ruby. In manchen anderen Sprachen gibt es dafür Standardbibliotheken, etwa System.Numerics.BigInteger in C# und java.math.BigInteger in Java. Go bietet mit math/big obendrein Unterstützung für gebrochene Zahlen; Perl-Programmierer müssen dafür auf die separaten Module bigint und bigrat zurückgreifen.

C++-Entwickler können Boost.Multiprecision verwenden, das seinerseits auf mehrere andere Umsetzungen zurückgreift, unter anderem auf die verbreitete GNU-Bibliothek libgmp. Wer will, kann die auch allein einsetzen – dank der in gmpxx.h definierten Operatoren sogar halbwegs komfortabel. C-Programmierer müssen selbstverständlich auf den Komfort verzichten, den ein Klassensystem mit überladenen Operatoren bietet. Allerdings steht die GMP-Bibliothek unter der Lesser General Public License (LGPL), während die Boost-eigene Implementierung der Boost Software License unterliegt. Das macht sie für manche Projekte zur besseren Wahl, obwohl sie langsamer rechnet als die GNU-Variante. Wer ohnehin vorhat, sein Programm unter die GPL zu stellen, kann auch die in C++ geschriebene Class Library for Numbers (CLN) von clisp-Autor Bruno Haible nutzen.

MPIR (Multiple Precision Integers and Rationals) ist ein Fork der GNU-Bibliothek, der ebenfalls unter der LGPL steht und mit libgmp kompatibel sein soll. Gegenüber dem Original bietet er den Vorteil, dass man unter Windows zum Übersetzen Microsofts Compiler verwenden kann – libgmp verlangt eine GNU-Umgebung wie Cygwin. Außerdem arbeiten die Entwickler an parallelen Algorithmen, die Multi-Core-Prozessoren und GPUs zum Rechnen nutzen.

Reelle Zahlen haben einen weit größeren Wertebereich als Integers, doch das Rechnen mit ihnen hat ebenfalls seine Tücken. Zusätzlich zu ungewollten Überläufen gilt es dabei, Rundungsfehler und Unterläufe zu vermeiden, die ein Ergebnis bis zur Unkenntlichkeit verfälschen können. Vor allem beim Subtrahieren zweier fast gleicher Zahlen macht sich die begrenzte Genauigkeit – 15 Dezimalstellen bei Double Precision – deutlich bemerkbar: Unter Umständen hat das Resultat nur noch ein paar signifikante Bits; schlimmstenfalls ist es null.

Zwar kann die Hardware Über- und Unterläufe in der Regel per Exception anzeigen, doch die Software muss solche Ausnahmen auch zur Kenntnis nehmen und darauf reagieren. Anders ausgedrückt: Der Programmierer muss jeden möglichen Über- oder Unterlauf vorhersehen und Vorkehrungen treffen, ihn zu umgehen – etwa, indem er eine alternative Rechenmethode verwendet.

Bei Berechnungen mit variabler Genauigkeit treten viele solcher Schwierigkeiten gar nicht erst auf. Allerdings ist der Nutzer dafür auf Bibliotheken angewiesen. libgmp bietet Floating-Point-Routinen; wer korrektes Runden im IEEE-Stil benötigt, ist allerdings mit den GNU-Libraries libmpfr für reelle und libmpc für komplexe Zahlen besser bedient. Boost.Multiprecision kann auf libgmp oder libmpfr sowie auf eine eigene Implementierung zurückgreifen. CLN bietet den Datentyp cl_LF mit „unbegrenzter“ Genauigkeit; allerdings ist der Exponent immer 32 Bit groß. Dasselbe gilt für Javas java.math.BigDecimal; da die Klasse mit einem 10er-Exponenten arbeitet, ist ihr Wertebereich jedoch um einiges größer.

In Ruby gibt es das Modul decimal sowie das neuere flt, das sowohl einen dezimalen als auch einen binären Gleitkomma-Datentyp bereitstellt. Python-Entwickler haben die Wahl zwischen dem Standardmodul decimal, dem in Python geschriebenen mpmath, dem auf libmpfr basierenden bigfloat und gmpy2. Letzteres macht Gebrauch von libmpfr und libmpc und kann daher auch mit komplexen Zahlen umgehen.

Alle Links: www.ix.de/ix1303137 (mr)