Ich habe eine Programmbibliothek geschrieben, die Funktionen enthält, um lange Zahlen zu addieren, subtrahieren und zu multiplizieren. Ein Beispielprogramm zeigt, wie man diese Funktionen verwendet.
Komplettes Paket (ZIP-File)
Programmbibliothek
Headerdatei der Bibliothek
Beispielprogramm, das die meisten Funktionen verwendet
Da wir es gewohnt sind im Dezimalsystem zu rechnen, verwendet diese Programmbibliothek auch diese Darstellung, damit man die Schritte besser nachvollziehen kann. Für einen Rechner wäre das Binärsystem besser geeignet, und wird auch in den erhältlichen Programmbibliotheken verwendet. Wenn bei einer arithmetischen Operation der gültige Zahlenbereich verlassen wird, so wird ein Übertrag gesetzt, der bei weiteren arithmetischen Operationen automatisch mit einbezogen werden kann. Es sind dann bei der Berechnung keine Zeitaufwendigen Abfragen und Sprünge notwendig, um zu überprüfen, ob der Zahlenbereich verlassen wurde.
In dieser Programmbibliothek werden folgende arithmetische Operatoren aufgeführt:
Um die langen Zahlen zu speichern, wird ein Speicherbereich reserviert, in
dem die einzelnen Ziffern hintereinander abgelegt werden. Ziffer
Bei der Addition wird für das Ergebnis ein Speicherbereich reserviert, der um eine Stelle größer ist als die größere der beiden zu addierenden Zahlen. Bei der Multiplikation werden die Anzahl der Stellen der beiden Zahlen addiert, um den Speicherbedarf des Ergebnisses zu ermitteln.
Die Addition wird wie oben im Beispiel aufgeführt durchgeführt.
Die Subtraktion ist der Addition sehr ähnlich. Ist die zu subtrahierende Ziffer größer, so wird eine eins von der nächst höheren Ziffer "geborgt".
Beispiel einer Multiplikation, wie wir sie von Hand durchführen würden:
Wir würden dies mit einer Reihe von einfachen Multiplikationen und Additionen lösen.
0
+ 4444 (ist 4*1111 um 0 Stellen verschoben)
+ 33330 (ist 3*1111 um 1 Stellen verschoben)
+ 222200 (ist 2*1111 um 2 Stellen verschoben)
+1111000 (ist 1*1111 um 3 Stellen verschoben)
========
1370974
Bei der Multiplikation wird zuerst die eine Zahl mit jeweils den Ziffern 0 bis 9 multipliziert, und das Ergebnis zwischengespeichert. Dies wird mit mpi_mulkurz() durchgeführt. Da wir sehr lange Zahlen haben, müßte man bei 200 Stellen auch 200 Multiplikationen durchführen. Hiervon würden sehr viele Multiplikationen mehrfach ausgeführt werden, da es nur zehn Ziffern gibt. Diese möglichen Multiplikationen kann man bereits vorher durchführen um Zeit zu sparen. Anschließend braucht man die berechneten Zahlen nur noch stellenrichtig zu addieren. Dies wird von der Routine mpi_addiere_free() ausgeführt. Es wird bei der niedrigsten Stelle begonnen, und je nachdem was für eine Ziffer dies ist (0 bis 9), wird die vorberechnete Multiplikation für diese Ziffer bei der Addition verwendet. Zusätzlich wird die vorberechnete Zahl um n Stellen verschoben, wenn die n-te Stelle berechnet wird.
Eine Division kann durch mehrfaches Subtrahieren gelöst werden. Die Anzahl der nötigen Subtraktionen liefert das Ergebnis der Division. Der Rest, der bei einer Ganzzahl Division anfällt, ist der Modulo. Um die Division zu beschleunigen, kann man z.B. Zehnerpotenzen des Nenners vom Zähler abziehen, sofern dieser dadurch noch kleiner ist als der Zähler.
Es wird bei der Darstellung die niederwertigste Ziffer links ausgegeben, und die höherwertigen Ziffern weiter rechts. Also 00315062 im Programm ist in der üblichen Schreibweise 26051300. Es wurden beim testen auch Berechnungen mit bis zu 17000 Stellen durchgeführt. Bei mehr Stellen kann es je nach eingestelltem Speichermodell, Betriebssystem und Rechnerarchitektur zu Fehlern kommen. Speziell bei einer Multiplikation wird sehr viel Speicher benötigt. Hier sollte der erste Parameter die kürzere Zahl enthalten, da dann weniger Speicher benötigt wird.
Beispiel Berechnung:
788539152479959923583473870729725158796647538883718863262181413347391236469
x
163117845256502920687558543656697020247411364462120385893160945804553250187472
604743326476435522680378897
=
012862480745292006410890272858478665047052244641713578041943468146981010437930
160098645877829367241942440036761175181846713094902521848685430625024876210479
4478806532579114244394693
Die ersten beiden Zahlen sind in den Dateien test1.txt und test2.txt abgelegt. In dem Programm main.cpp werden zwei zufällige Zahlen addiert, subbtrahiert und multipliziert. Anschliessend wird die für 100 Multiplikationen benötigte Zeit gemessen. Danach wird die oben aufgeführte Beispiel Berechnung durchgeführt. Das Ergebnis wird in der Datei test3.txt abgelegt. Beim Lesen und Schreiben der Dateien werden die Zahlen in das richtige Format gewandelt. Zahlen <--> ASCII-Zeichen und Darstellung 0001 <--> 1000.
Das Programm wurde unter DOS Borland C 3.1 mit dem Speichermodell Small compiliert. Wird ein anderes Speichermodell gewählt, bei dem für die Daten FAR Zeiger verwendet werden, dann dauert die Berechnung länger. Es wurde 100 mal eine Multiplikation mit jeweils zwei 1000 stelligen Zahlen ausgeführt. Dabei benötigt ein Pentium 90 ca. 80s, ein Pentium 200 benötigt hierfür 38s.