In der Informatik bezeichnet Langzahlarithmetik die Implementierung arithmetischer Rechenoperationen mit Zahlen, deren Zahlenbereich und Genauigkeit nur durch den verfügbaren Arbeitsspeicher begrenzt ist (engl. arbitrary precision numbers). Diese Implementierungen sind meistens in Software realisiert und werden notwendig, wenn die Anzahl signifikanter Stellen der sonst verwendeten, schnelleren Hardware-Implementierung der arithmetisch-logischen Einheit des Prozessors nicht mehr ausreicht. Entstehen beim Rechnen mit der Hardware-Variante Ergebnisse, die eine höhere Anzahl Stellen erfordern als vorhanden sind, so tritt ein Überlauf auf, und das erhaltene Ergebnis ist nur noch ein Divisionsrest des exakten Ergebnisses. In der Langzahlarithmetik werden Überläufe durch die Verwendung erweiterbarer (skalierbarer) Zahlendarstellungen vermieden. Sie ist aus dem Rechnen mit doppelter Genauigkeit entstanden und stellt eine Verallgemeinerung dar.
Viele Programmiersprachen und Computeralgebrasysteme bringen bereits Erweiterungen zum Rechnen mit Langzahlen in verschiedenen Formaten mit.
Typische Anwendungen sind Rechenverfahren der Kryptologie, in denen oft sehr große Primzahlen verwendet werden und numerische Anwendungen mit erhöhten oder unbekannten Genauigkeitsanforderungen.
Zahlenformate
BearbeitenDie folgenden Zahlenformate sind gebräuchlich:
- Ganzzahlen: Der einfachste Datentyp besteht aus einem Vorzeichen und dem Absolutwert. Ein Beispiel ist . Die Größe der Datenstruktur für den Absolutwert wächst mit ihm nach Bedarf.
- Brüche: Dieser Datentyp besteht aus einem Vorzeichen und zwei Absolutwerten, jeweils ein Wert für den Zähler und Nenner. Ein Beispiel ist . Die kompakteste Repräsentation entsteht, wenn der Zähler und Nenner teilerfremd sind.
- Gleitkommazahlen: Dieser Datentyp besteht aus einer Mantisse (Vorzeichen und Absolutwert) und einem Exponenten (Vorzeichen und Absolutwert). Ein Beispiel ist in normalisierter Exponentialdarstellung. Hier sind Absolutwerte von Mantisse und Exponent dynamische Datenstrukturen.
- komplexe Gleitkommazahlen: Dieser Datentyp besteht aus zwei Gleitkommazahlen, häufig eine Zahl für den Realteil und eine für den Imaginärteil. Ein Beispiel ist .
Mit diesen Datentypen wird die Klasse der berechenbaren Zahlen abgedeckt. Reelle Zahlen lassen sich im Allgemeinen nicht durch Turingmaschinen exakt darstellen, da die Mächtigkeit der Menge der reellen Zahlen größer ist als die der Menge der ganzen Zahlen .
In allen Datentypen werden die Absolutwerte durch sequentielle Datenstrukturen variabler Länge dargestellt (z.B. durch dynamisch allozierte Listen oder Felder). Dazu wird jeweils soviel Speicher vom Freispeicher angefordert, wie es die Größe des Absolutwerts grade erfordert.
sequentielle Algorithmen
BearbeitenDie sequentiellen Rechenverfahren stellen die grundlegenden Operationen der Arithmetik für Langzahlen zur Verfügung.
- Addition: Beim Addieren von Gleitkommazahlen werden die Operanden zuerst so normalisiert, so dass beide Operanden gleich viele Nachkommastellen besitzen bzw. den gleichen Exponenten verwenden. Allgemein sind beim Addieren Überträge (bzw. Überläufe) kleinerer Stellen zu berücksichtigen. In der Regel wird die Addition daher von den niederwertigen zu den höherwertigen Einheiten berechnet, wobei ein Übertrag der letzten Teiladdition mit addiert wird.
- Subtraktion: Die Subtraktion erfolgt analog zur Addition. Ein zuvor aufgetretener Übertrag ist mit abzuziehen.
- Multiplikation: Der Karazuba-Algorithmus benötigt weniger Operationen als die Realisierung der Schulmethode zur schriftlichen Multiplikation zweier Zahlen. Spätere Entwicklungen sind der Toom-Cook-Algorithmus, der Schönhage-Strassen-Algorithmus und der Algorithmus von Fürer[1].
- Division: Goldschmidt-Division und SRT-Division
- Potenzierung: Binäre Exponentiation für natürliche Exponenten, für rationale Exponenten mit Wurzelziehen, für positive Basen mithilfe des natürlichen Logarithmus, für beliebige Basen ungleich 0 und beliebige Exponenten komplexe Exponentiation
Programmiersprachen
BearbeitenZahlreiche Programmiersprachen und Computeralgebrasysteme unterstützen Langzahlarithmetik entweder durch eingebaute Datentypen, oder durch Erweiterungen aus Bibliotheken. Eine Liste verfügbarer Software bietet die englische Wikipedia. Im Projekt Rosettacode gibt es eine Programmieraufgabe[2], die Langzahlarithmetik zum Lösen erfordert. Dort sind Lösungen in vielen verschiedenen Programmiersprachen einzusehen.
Anwendungen
BearbeitenAnwendungen für Arithmetik mit erhöhten Genauigkeitsanforderungen liegen zahlreich in den Bereichen numerische Mathematik, Informatik, Physik und Ingenieurswissenschaften vor.
- Informatik:
- In asymmetrischen Kryptosystemen aus der Informatik werden häufig große Primzahlen zur Schlüsselgenerierung eingesetzt, um den Aufwand zum Knacken der Verschlüsselung zu erhöhen.[3][4]
- in symbolisch rechnenden Computeralgebrasystemen zur Ausgabe eines Ergebnisses in numerischer anstelle der üblichen symbolischen Darstellung.
- numerische Mathematik:
- bei der Berechnung von Mittelwerten zur Vermeidung von Überlaufen.
- bei der Berechnung von Konstanten aus langsam konvergierenden Reihen, damit Rundungsfehler vermieden werden.
- bei der Berechnung von Determinanten schlecht konditionierter Matrizen (z.B. Hilbertmatrizen).
- bei der Berechnung von Fraktalen (wie z.B. der Mandelbrotmenge) zur Erreichung hoher Zoomfaktoren bzw. Auflösungen[5].
- Astronautik/Astronomie/Physik
- Bahnberechnungen in astronomischen Maßstäben (Wiedereintritt, Andockmanöver, Landemanöver).
Geschichte
BearbeitenLaut Donald E. Knuth[6] wurden die ersten Computer-Algorithmen für das Rechnen mit doppelter Genauigkeit von John v. Neumann und Herman Goldstine im Jahr 1947 veröffentlicht[7]. Implementierungen für Gleitkommazahlen erweiterter Genauigkeit für die Computersprachen FORTRAN (1963) [8] [9] und ALGOL (1966) [10] sowie die erste Implementierung für Ganzzahlen beliebiger Genauigkeit (1966) [11] werden in Knuth[12] erwähnt.
Web Links
Bearbeiten- GMP C Bibliothek für mehrfachgenaue Ganzzahl- und Gleitkommarechnungen
- MPFR C Bibliothek für mehrfachgenaue Gleitkommarechnungen
- ttmath kleine C++ Bibliothek für mehrfachgenaue Ganzzahl- und Gleitkommarechnungen
- Wikipedia Liste von Langzahlarithmetik-Software nach Bibliotheken, Programmen und Programmiersprachen(englisch)
- RealLib eine in C++ geschriebene Bibliothek zur Berechnung von reellen Zahlen.
- iRRAM eine in C++ geschriebene Bibliothek zur Berechnung von reellen Zahlen.
- iX-Artikel 'Grosse Nummern' kleiner Artikel zu verschiedenen frei verfügbaren Langzahl-Bibliotheken.
Siehe auch
BearbeitenQuellen
Bearbeiten- ↑ Martin Fürer: Faster integer multiplication (PDF; 295 kB), STOC 2007 Proceedings, S. 57–66.
- ↑ Rosettacode.org zeigt eine Programmieraufgabe zur Berechnung der Potenz (183231 Dezimalstellen) mit Lösungen in vielen Programmiersprachen mithilfe von Langzahlarithmetik (englisch).
- ↑ Researchers: 307-digit key crack endangers 1024-bit RSA Sicherheitsforscher: Kompromittierung eines 307-stelligen Schlüssels stellt 1024-Bit RSA-Schlüssel infrage.
- ↑ http://www.rsa.com/rsalabs/node.asp?id=2218 empfiehlt für wichtige RSA-Schlüssel Längen von 2048 Bits (entspricht ungefähr 600 Stellen).
- ↑ FractInt: Arbitrary Precision and Deep Zooming
- ↑ Donald E. Knuth: The Art Of Computer Programming, Volume 2. 2. Auflage, Addison Wesley: Reading Massachusetts 1981 (1969), ISBN 0-201-03822-6, S. 263.
- ↑ John von Neumann: Collected works, Part 5. Design of computers, theory of automata and numerical Analysis. Pergamon Press: New York, 1963, ISBN 978-008-009571-4, ISBN 0-08-009571-2, S. 141-151.
- ↑ A. H. Stroud und D. Secrest: A multiple-precision floating point interpretive program for the Control Data 1604, In: The Computer Journal, Volume 6, Issue 1, 1963, S. 62-66. (online: http://comjnl.oxfordjournals.org/content/6/1/62.full.pdf+html)
- ↑ B. I. Blum: An extended arithmetic package, In: Communications of the ACM, Volume 8, No. 5, 1965, S.318-320.
- ↑ M. Tienari und V. Suokonautio: A set of procedures making real arithmetic of unlimited accuracy possible within ALGOL 60, In: BIT Numerical Mathematics, Volume 6, Issue 4, 1966, S. 332-338.
- ↑ G. E: Collins: PM, a system for polynomial manipulation, In: Communications of the ACM, Volume 9, No. 8, 1966, S.578-589.
- ↑ Donald E. Knuth: The Art Of Computer Programming, Volume 2. 2. Auflage, Addison Wesley: Reading Massachusetts 1981 (1969), ISBN 0-201-03822-6, S. 265.
Kategorie:Software Kategorie:Numerische Mathematik Kategorie:Computerarithmetik
