Multiplikation großer ZahlenHallo, in diesem Tutorial geht es um die Multiplikation von Zahlen, die weit über die Maxima von integer und integer64 hinaus gehen. Benötigt werden diese allerdings in Stringform.
Hintergrund:Das Prinzip, welches ich hier vorstelle, basiert auf der Vedischen Multiplikation.
Dieses Prinzip lässt sich wunderbar zur schriftlichen Multiplikation heranziehen, falls man gerade mal keinen Taschenrechner zur Hand hat.
Zuerst ein einfaches Beispiel mit zwei Zwei-Stelligen Zahlen:
(die Nullen dienen allein zur Formatierung)Zuerst berechnet man das Produkt von 4 und 6, die letzte Stelle wird notiert und die anderen Stellen gemerkt oder notiert.
In diesem Falle ist die Zahl
4 und der übertrag
2Danach werden die beiden letzten Stellen der Zahlen über Kreuz multipliziert und anschließend addiert, der übertrag der letzten Rechnung wird aufaddiert.
| Zitat: |
| 3 * 6 + 5 * 4 + 2 = 40 |
Also ist unsere Zahl
0 und der übertrag ist
4Jetzt werden die ersten Stellen multipliziert und der übertrag addiert:
unsere Zahl ist
9 und der übertrag ist
1jetzt sind wir fertig, der übertrag wird noch vorne drangehängt, da wir alle Stellen abgearbeitet haben und nur noch Null-Stellen übrig sind.
Unser ergebnis ist demnach
1904.
Bei größeren Zahlen wird das ganze ein wenig komplizierter, wir brauchen pro zusätzliche Stelle zwei weitere Schritte, bei 3 Stellen sähe das so aus:
Bei 4 Stellen hätten wir diese dreifache Überkreuzung wiederrum 2 mal und dazwischen eine größere.
Möchte man eine zwei Zahlen mit unterschiedlicher Stellenzahl multiplizieren, so kann man die kleinere Zahl vorne mit Nullen auffüllen.
Wer mehr über vedische Mathematik erfahren will, kann einen Blick hier hinein werfen:
www.vedicmaths.org/I...utorial/Tutorial.aspDieses Prinzip kann ebenfalls auf andere Basen, so zB für Oktal, Hexadezimal und Binärsysteme angewandt werden!
Die Implementation:Als ich
Corpsman davon erzählt habe, hat er dies auch gleich in einen Algorithmus umgesetzt, dieser ist hier zu finden:
tyrann.deadbyte.de/c...ische_multiplicationTrotzdem möchte ich hier etwas genauer darauf eingehen.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
| function VedicMulti(a, b: string): string;
var
len, i, j: integer;
num: int64;
begin
result := '';
num := 0;
len := max(length(a), length(b));
while length(a) < len do
a := '0' + a;
while length(b) < len do
b := '0' + b;
for i := 1 to len do
begin
for j := 1 to i do
num := num + strtoint(a[len - j + 1]) * strtoint(b[len - i + j]);
result := inttostr(num mod 10) + result;
num := num div 10;
end;
for i := len - 1 downto 1 do
begin
for j := 1 to i do
num := num + strtoint(a[j]) * strtoint(b[i - j + 1]);
result := inttostr(num mod 10) + result;
num := num div 10;
end;
result := inttostr(num) + result;
while Pos('0', result) = 1 do
delete(result, 1, 1);
end; |
Der Algo ist im Grunde genommen der gleiche wie der von
Corpsman, eine rekursive Implementation ist ebenfalls möglich und werde ich eventuell noch nachreichen, bisher ist mir diese leider noch nicht geglückt ;)
Der Algo berechnet zunächst die Länge der längsten Zahl, dann wird die kürzere Zahl (falls vorhanden) mit Nullen aufgefüllt. Die doppelte Länge minus 1 ergibt die Anzahl der benötigten Schritte. Zuerst wird von rechts zur Mitte gearbeitet und im zweiten Schritt von der Mitte nach links. Dabei sorgt die äußere Schleife für das Durchgehen aller Schritte und die innere Multipliziert und addiert die Ziffern über Kreuz. Am Ende wird jeweils die Zahl berechnet und gespeichert, sowie der übertrag berechnet (mod 10 liefert die letzte Stelle und div 10 alles davor). Im nächsten Iterations-Schritt wird der zuvor berechnete übertrag dazu
addiert und der nächste Wert berechnet. Am ende wird noch der letzte übertrag (der auch 0 sein kann) vorne angefügt und alle überflüssigen Nullen entfernt.
Der Grund, warum diese Algo so große Zahlen berechnen kann, liegt darin, dass die einzige Integer Variable mit der gerechnet wird, der übertrag ist, und dieser ist immer recht klein. Durch die Verwendung von int64 lässt sich diese Grenze noch ausweiten (wie bereits im Algo geschehen). die zweite Beschränkung sind die Schleifenvariablen und die Variable zum Speichern der Länge des Strings. Hier kann man ebenfalls noch auf int64 umsteigen.
Alles in allem aber lassen sich mit diesem Algo sehr schnell extrem große Zahlen berechnen, bei denen der Windows Taschenrechner nicht mehr mitreden kann.
Vielen Dank an
Corpsman für den Algorithmus.
Ich hoffe es war lustig und lehrreich und jemand kann es gebrauchen.
Weiterführende Links:(Video mit Erklärung von Vedischer Multiplikation)www.metacafe.com/wat...fast_multiplication/ (Tutorial zur Vedischen Mathematik)www.vedicmaths.org/I...utorial/Tutorial.asp(Demo Programm von Corpsman mit Source)tyrann.deadbyte.de/c...ische_multiplicationmfg
)
