Dieser Artikel ist im Heise-Verlag in der Zeitschrift "c't", Ausgabe 04/1989 erschienen.
Er ist hier aus Gründen der besseren Übersicht dreigeteilt. Der Text ist Grundlage des Artikels
"Primzahltests und Primfaktorzerlegung". Links:
Wofür lange Zahlen?
Die Compiler und Interpreter der verschiedenen Programmiersprachen
reservieren für Integerzahlen gewöhnlich ein Maschinenwort, auf
einem PC also 16 Bit. Der dadurch erhaltene Rechenbereich
erstreckt sich von -32768 bis 32767, was keine großartigen
Anwendungen zuläßt. "Long Integer"-Zahlen, wie sie beispielsweise
in C, aber auch in anderen Sprachen zur Verfügung gestellt werden,
belegen zwei Maschinenworte, was den Bereich immerhin auf das
Intervall von -2147483648 bis 2147483647 ausdehnt.
In vielen Fällen ist das akzeptabel, oft sind jedoch Integer-
Zahlen beliebiger Länge erforderlich. Geht es etwa um die Frage
großer Primzahlen, wie sie beim RSA-Algorithmus, einem Verfahren
zur Verschlüsselung von Texten, Verwendung finden, sind sie
eigentlich unerläßlich. Ebenso werden sie benötigt, will man Sätze
aus der Primzahltheorie rechnerisch nachvollziehen oder
Vermutungen widerlegen. Schließlich finden sie Anwendung bei der
Jagd auf "Rekord-Primzahlen".
Die Datenstruktur
Um derartige Fragen anzugehen, müssen zunächst derartige lange
Integer-Zahlen implementiert werden. Als erstes ist hierbei die
Wahl der Programmiersprache wichtig. Denn bereits so grundlegende
Operationen wie Multiplikation und Division sind sehr
zeitintensiv. Es bietet sich daher C an, weil man damit sehr
maschinennah, aber doch unabhängig vom verwendeten Rechner
programmieren kann. Und Maschinennähe ermöglicht nun einmal eine
hohe Geschwindigkeit des erzeugten Codes.
Der nächste Schritt ist die Wahl der zugrunde gelegten
Datenstruktur, d.h. die Frage: Auf welche Weise repräsentieren wir
eine "longint"-Zahl im Speicher des Rechners. Auch dies ist ein
wichtiger Punkt, der bei der Programmierung der Rechenoperationen
einen positiven oder negativen Ausschlag geben kann. Geeignet ist
natürlich nur ein Vektor, da alle skalaren Datentypen zu klein
sind, Strukturen hingegen in der Größe beschränkt. Bei Vektoren
kann jedoch durch einfaches Ändern der Obergrenze auch die Größe
variiert werden.
Als Elementtyp empfiehlt sich der Typ "long", da dies der größte
skalare Typ ist. In einer "typedef"-Anweisung vereinbaren wir den
Typ "longint" als Vektor von long-Zahlen. Zum Beispiel:
#define MaxNr 10
typedef long longint[MaxNr];
|
Damit kennen wir aber noch nicht den Wert einer Zahl,
wenn uns der zugehörige Vektor bekannt ist. Wir müssen dazu noch
wissen, wie der Inhalt eines longint-Vektors zu interpretieren
ist.
Erste Variante der Darstellung und ihr Problem
Nun wissen wir, daß die größte darstellbare long-Zahl
2147483647 ist. Wir könnten sagen, wir ignorieren die erste
Ziffer, die ja nur die Werte 0, 1 und 2 annehmen kann und
verwenden die restlichen Ziffern zur Darstellung aller Zahlen von
0 bis 999999999. Dies wäre der Beitrag eines Vektor-Elements. Die
Gesamtzahl erhielten wir einfach durch Aneinanderhängen der
Ziffern.
Auf diese Weise würde z.B. die Zahl 12345678912345 im Vektor a
dargestellt durch a[1]=12345 und a[0]=678912345. Wir sprechen hier
von einer dezimalen Interpretation, da wir die Zahl als
Zeichenkette ansehen, deren Bestandteile dezimal dargestellt in
den einzelnen Vektor-Elementen gespeichert sind. Diese Art der
Interpretation hat einige Vorteile: Sämtliche Operationen lassen
sich relativ leicht programmieren, da wir nur in dem uns
vertrauten Dezimalsystem denken müssen.
Bei vielen Operationen müssen Überträge berücksichtigt werden, die
dem nächst höheren Element zugerechnet werden. Diese lassen sich
leicht erkennen, da wir über eine "redundante", d.h. überzählige,
Ziffer verfügen. Und schließlich ist die Ausgabe einer derartigen
Zahl auch kein Problem. Wir wollen sie natürlich im Dezimalsystem
auf dem Bildschirm sehen, hierzu ist keinerlei Umformung
notwendig, denn die einzelnen Elemente müssen nur
aneinandergehängt werden.
Leider ist diese Methode auch mit Nachteilen verbunden. Und die
offenbaren sich ausgerechnet bei unserem ersten Anliegen, nämlich
der Geschwindigkeit. Als "schnell" müssen beispielsweise die
sogenannten Bit-Operationen angesehen werden. Diese sollte man so
oft wie möglich einsetzen. Bei der Erkennung eines Übertrags fängt
es aber bereits an. Hier könnte man bei geschickter
Implementierung mit dem Inspizieren eines einzigen Bits auskommen.
Bei der dezimalen Interpretation kommt man hingegen um den
Vergleich mit einer long-Zahl nicht herum. Dies hätte für uns
fatale Auswirkungen, da die Übertrags-Prüfung bei den Grund-
Operationen bereits ständig auftritt und diese so zur langsamen
Schnecke werden läßt. An anderen Stellen sieht es ähnlich aus.
Dies läßt nur eine Konsequenz zu: Wir vergessen die dezimale
Interpretation unseres Vektors und sehen diesen lieber als Kette
von Bits an.
Und so machen wir es wirklich
Bei dieser binären Interpretation verschenken wir kein einziges
Bit. Von jedem Vektor-Element werden 32 Bits geliefert. Den
gesamten Vektor sehen wir als riesige Bit-Kette an. Wie erfahren
wir nun den Wert der longint-Zahl? Nun, wir denken uns einfach den
Maximalwert eines Elements als Basis unserer Zahldarstellung. Also
sei B=2^32=4294967296. Der Wert des Vektors a ist demnach
a[0]+a[1]*B+a[2]*B^2+a[3]*B^3+a[4]*B^4... Unsere eben betrachtete
Zahl 12345678912345 hätte nun also die Darstellung a[1]=2874 und
a[0]=1942903641.
Da taucht aber ein Problem auf, das wir eben noch nicht hatten:
Das Erkennen eines Übertrags wird jetzt schwierig. Denn ist die
Summe zweier long-Zahlen zu groß, wird das überzählige Bit vom
System einfach weggelassen. Hier müßten wir uns mit komplizierten
Algorithmen helfen, die z.B. vor der Addition schon Überprüfungen
anstellen und hinterher Konsequenzen ziehen. Das ist nicht ideal,
da es wieder Zeit kostet. Daher führen wir einfach das ein, was
wir bei der dezimalen Interpretation automatisch hatten, nämlich
ein redundantes Bit.
D.h. wir benutzen zur Speicherung der Zahl nur jeweils 31 Bit
einer long-Zahl, das letzte wird nur zur Erkennung eines Übertrags
verwendet. Dieses ist natürlich das höchstwertige Bit. Ist es
gesetzt, wird die long-Zahl negativ, was wir leicht prüfen können.
Genauso könnten wir übrigens Elemente vom Typ "unsigned long"
nehmen. Einen Übertrag könnten wir dann mit Hilfe des Operators &
erkennen. Angesichts der Tatsache, daß dieser Typ bei vielen
Compilern fehlt, bleiben wir bei long-Zahlen, die denselben Zweck
erfüllen. Unsere Beispielzahl wird nun durch a[1]=5748,
a[0]=1942903641 dargestellt.
Eine letzte Änderung betrifft die höheren Elemente kleiner Zahlen.
Ist MaxNr etwa auf 50 gesetzt, wird natürlich auch die Zahl 1
durch 50 long-Elemente repräsentiert. Klar ist, daß hier a[0]=1
sein muß. Hingegen stellt sich die Frage, was mit den 49 anderen
Elementen geschieht. Wir könnten sie z.B. alle auf 0 setzen. Dann
müßten jedoch bei jeder Operation alle 50 Elemente berücksichtigt
werden, für eine derart kleine Zahl ein nicht zu vertretender
Aufwand. Eine andere Möglichkeit wäre, beim ersten nicht benutzten
Element das höchstwertige Bit zu setzen, um so das Ende der Zahl
zu kennzeichnen. So hätten wir auch eine weitere Rechtfertigung,
dieses Bit zur Zahlendarstellung unbenutzt zu lassen.
Jedoch müßten wir auf diese Art ständig eine zusätzliche Abfrage
programmieren, die testet, ob dieses Bit gesetzt ist. Als
günstiger hat es sich erwiesen, das erste Element des Vektors
nicht zur Zahlendarstellung zu benutzen. Vielmehr wollen wir hier
die Anzahl der benutzten Elemente des Vektors hineinschreiben. So
ist von Anfang an bekannt, wie lang die jeweilige Zahl ist. Um zu
dieser Darstellung zu gelangen, muß alles einfach um ein Element
verschoben werden. Bei unserer Beispielzahl etwa werden zwei
Elemente benutzt, dies steht in a[0]. Die Zahl wird insgesamt
durch a[2]=5748, a[1]=1942903641 und a[0]=2 repräsentiert.
Fassen wir also zusammen: Eine longint-Zahl wird in einem Vektor
von long-Zahlen gespeichert. Das Element Nr.0 dieses Vektors gibt
die Anzahl der Elemente an, die zur Darstellung der Zahl benutzt
werden. Bei jedem dieser Elemente werden die Bits 0 bis 30 zur
Zahldarstellung verwendet, Bit 31 dient dem Erkennen eines
Übertrags. Und was man betonen sollte: Es gibt keine negativen
longint-Zahlen.
Die Art der Repräsentation der longint-Zahlen erlaubt eine
einfache Initialisierung mittels geschweifter Klammern. So ist es
auch leicht möglich, einige longint-"Konstanten" zu definieren,
wie das für die Zahlen 1,2,3,4,10 und 100 geschehen ist. Natürlich
sind das keine wirklichen Konstanten, sie sollten aber vom
Anwender so behandelt und nicht geändert werden.