4. Karazuba-Multiplikation
Wir lassen jetzt JavaScript zwei 1000-stellige Zahlen multiplizieren (10000 mal hintereinander) und messen die Rechenzeit dafür:
Nun wiederholen wir das Experiment mit doppelt so langen (2000-stelligen) Zahlen.
Nach unseren Überlegungen zur schriftlichen Multiplikation sollte die Rechnung nun 2² = 4 mal so lange dauern.
Wie hat sich bei der Zeitbedarf erhöht? Stimmt das mit unserer Vorhersage überein?
Für mathGUde 2 konnte ich schreiben:
„Sie werden bei Ihrer Messung bemerkt haben, dass die Multiplikation doppelt langer Zahlen nicht – wie erwartet – viermal so lange gedauert hat, sondern nur dreimal so lang. Das liegt daran, dass Python eine verbesserte Methode, die sogenannte Karatsuba-Multiplikation verwendet.“
Sie können aus dem Ergebnis des Experiments also schließen: JavaScript hat die Karazuba-Multiplikation nicht implementiert.
Der Trick von Karazuba
Wir betrachten die Multiplikationsaufgabe 1234 · 5678. Wenn wir je zwei Ziffern als Einheit betrachten (man kann sie als Ziffer im Stellenwertsystem zur Basis 100 auffassen), bekommen wir:
1234 · 5678
─────────────
34·78
12·78+34·56
12·56
─────────────
104·12·56 + 102(12·78 + 34·56) + 34·78
Wir haben also vier einzelne Multiplikationen von zweistelligen Zahlen. Für jede dieser vier Multiplikationen benötigen wir wieder vier Multiplikationen von einstelligen Zahlen. Auch so kommen wir auf die 4·4 = 16 Basismultiplikationen. Der russische Mathematiker A. Karazuba hat 1960 mit einen einfachen Trick die Methode verbessert:
Im gelben Ausdruck stecken zwei der vier Produkte. Wenn man ihn so umformt:
12·78 + 34·56 = (12+34)·(56+78) - 12·56 - 34·78
hat man zwar aus zwei Produkten drei gemacht. Aber zwei davon haben wir ja sowieso schon berechnet. Insgesamt benötigen wir so nur drei statt vier Produkten, das bedeutet, wir haben 25% eingespart! Grafisch ist das in der Abbildung (Stufe 1) dargestellt. Jetzt können Sie sich auch das Ergebnis des Tests erklären: Python verwendet automatisch die Karazuba-Multiplikation.
25% Ersparnis sind zwar ganz hübsch, aber der eigentliche Vorteil der Karazuba-Multiplikation liegt darin, dass sich die Ersparnis umso mehr steigert, je größer die zu multiplizierenden Zahlen sind. Im Beispiel 1234 · 5678 bestehen ja die Faktoren der drei Einzelmultiplikationen aus zweistelligen Zahlen, und hier können wir wieder den Trick anwenden, z. B.
12·56 = 1·5·100 + (1·6 + 2·5)·10 + 2·6
= 1·5·100 + ((1+2)·(6+5)-1·5-2·6)·10 + 2·6
Jetzt haben wir zweimal gespart: Zunächst haben wir 1234 · 5678 in drei statt vier Multiplikationen mit zweistelligen Faktoren zerlegt. Bei jeder dieser drei Multiplikationen sparen wir wieder ein Viertel ein. Die gesamte Rechenzeit verkürzt sich also auf (3/4)·(3/4) = 9/16 (Abbildung: Stufe 2).
Je größer also die Faktoren sind, umso drastischer zahlt sich der Vorteil der Karazuba-Multiplikation aus! Multiplizieren wir z.B. zwei 64-stellige Zahlen miteinander, haben wir 6 Halbierungen bis zu einstelligen Zahlen (64 = 26). Damit verkürzt sich die Rechenzeit auf (3/4)6, das ist etwa 0,178 (Abbildung, Stufe 6). Hier sparen wir also schon über 80% gegenüber der Standardmethode!
Die Anzahl S(n) der Einzelmultiplikationen bei der Multiplikation zweier n-stelliger Zahlen mit der schriftlichen Multiplikation ist S(n) = n^2.
Wenn die Stellenzahl eine Zweierpotenz ist, haben wir S(2^n) = 4^n.
Bei der Karazuba-Multiplikation erhalten wir entsprechend K(2^n) = 3^n.
Damit bekommen wir
\begin{aligned}
K(n) & = & K(2^{log_2 n}) \\
& = & 3^{log_2 n} \\
& = & (2^{log_2 3})^{log_2 n} \\
& = & 2^{log_2 n\cdot log_2 3} \\
& = & n^{log_2 3} \approx n^{1.59}
\end{aligned}
Der entscheidende Vorteil ist also nicht, dass wir den Algorithmus um einen bestimmten Prozentsatz schneller gemacht haben (das könnte man auch mit einem schnelleren Computer oder Code-Optimierung erreichen).
Entscheidend ist vielmehr, dass wir von einem quadratischen Wachstum (n^2) mit der Größe der Faktoren zum Wachstums mit nur n^{1.59} gekommen sind.
Bitte machen Sie sich klar, dass der schnellste Computer der Welt (auch der Zukunft) mit dem klassischen Multiplikationsverfahren, ab einer gewissen Größe der Faktoren dem langsamsten Computer der Welt unterlegen ist, wenn dieser die Karazuba-Multiplikation verwendet. Denn das Verhältnis von n^2 zu n^{1.59} wächst ja mit n über alle Grenzen!
Die folgende Prinzip-Implementierung lädt Sie zum Experimentieren ein:
Damit machen wir einen Test (ohne Ergebnisausgabe, weil das den Zeitbedarf verfälscht):
Die Funktion bestätigt zwar die Zeitkomplexität der Karazuba-Multiplikation. Ersetzen Sie aber mal die Karazuba-Multiplikation mit der „schlechten“ JavaScript-Multiplikation! Dann werden Sie zum ernüchternden Fazit kommen: Die Ineffizienz einer interpretierten JavaScript-Funktion vereitelt die Optimierung. Die Karazuba-Multiplikation müsste vom Browser-Hersteller im Java-Script-Interpreter implementiert werden.
Weiter zu: Unwahrscheinliche Würfel und verwechselte Briefe
