# Eine kurze Geschichte der Multiplikation

1. Multiplikation durch Addition
2. Binäre Multiplikation
3. Parallele Multiplikation
4. Karatsuba-Multiplikation

## 4. Karatsuba-Multiplikation

Wir lassen nun Python zwei 10000-stellige Zahlen multiplizieren (100 mal hintereinander) und messen die Rechenzeit dafür:

    import time
    a = rand(10^10000)
    b = rand(10^10000)
    start = time.clock()
    for i in range(100):
        c = a * b
    end = time.clock()
    zeit10000 = end-start
    print("Rechenzeit für 10000 Stellen: {:0.3f} s".format(zeit10000))

Nun wiederholen wir das Experiment mit doppelt so langen (20000-stelligen) Zahlen.
Nach unseren Überlegungen zur schriftlichen Multiplikation sollte die Rechnung nun 2² = 4 mal so lange dauern.

    a = rand(10^20000)
    b = rand(10^20000)
    start = time.clock()
    for i in range(100):
        c = a * b
    zeit20000 = time.clock() - start
    print("Rechenzeit für 20000 Stellen: {:0.3f} s".format(zeit20000))
    print("20000 Stellen benötigen {:0.2f} mal soviel Zeit wie 10000 Stellen"
          .format(zeit20000/zeit10000))

Wie hat sich bei der Zeitbedarf erhöht? Stimmt das mit unserer Vorhersage überein?

Stufe 1
Stufe 2
Stufe 3
Stufe 4
Stufe 5
Stufe 6

### Der Trick von Karatsuba

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.

Um diese Methode zu verstehen, kommen wir nun nochmals auf die Aufgabe 1234 · 5678 zurück. 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. Karatsuba 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 nebenstehenden Abbildung (Stufe 1) dargestellt. Jetzt können Sie sich auch das Ergebnis des Tests erklären: Python verwendet automatisch die Karatsuba-Multiplikation.

25% Ersparnis sind zwar ganz hübsch, aber der eigentliche Vorteil der Karatsuba-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 Karatsuba-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) = n2.
Wenn die Stellenzahl eine Zweierpotenz ist, haben wir S(2n) = 4n.
Bei der Karatsuba-Multiplikation erhalten wir entsprechend: K(2n) = 3n.

Damit bekommen wir

\begin{eqnarray} 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{eqnarray}

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 (n2) mit der Größe der Faktoren zum Wachstums mit nur n1.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 Karatsuba-Multiplikation verwendet. Denn das Verhältnis von n2 zu n1.59 wächst ja mit n über alle Grenzen!