Eine kurze Geschichte der Multiplikation

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

Auch scheinbar einfache Algorithmen lassen sich oft noch optimieren.
In dieser Präsentation untersuchen wir, ob die aus der Schule bekannte schriftliche Multiplikation noch Verbesserungspotenzial hat.

1. Multiplikation durch Addition

Falls Sie sich noch an das schriftliche Rechnen in der Schule erinnern oder jemals in die Verlegenheit kamen, nur mit Bleistift und Papier eine größere Multiplikation durchzuführen, werden Sie sich erinnern, dass Multiplizieren viel aufwendiger ist als Addieren. Woran liegt das?

Nehmen Wir einmal an, Sie können das kleine Einmaleins auswendig und damit zwei einstellige Zahlen ebenso schnell multiplizieren wie addieren.
Nun probieren Sie bitte einmal, zwei vierstellige Zahlen schriftlich zu addieren und zu multiplizieren.
Sieht Ihr Zettel etwa so aus:

   1234      1234·5678
  +5678      ─────────
   ────           9872   
   6912          8638
                7404
               6170
             ─────────
               7006652

Wie verhält sich die Rechenzeit zur Größe der Zahlen beim schriftlichen Multiplizieren?

Wir haben jede Ziffer des linken Faktors mit jeder Ziffer des rechten Faktors multipliziert. Im Beispiel haben wir 4·4 = 16 Einzelmultiplikationen durchgeführt.
Für das Produkt zweier n-stelliger Zahlen brauchen wir also n² einzelne Multiplikationen. Dazu kommt noch das Aufaddieren am Ende, das aber am gesamten Rechenaufwand bei großen Zahlen kaum eine Rolle spielt. Die Zeit ist demnach proportional zum Produkt der Längen beider Zahlen.
Zum Vergleich: Beim schriftlichen Addieren zweier n-stelliger Zahlen braucht man nur n Additionen von einzelnen Ziffern (und maximal noch einmal so viele Additionen für die Überträge). Die Rechenzeit steigt hier also nur linear mit n an!

Die relative Einfachheit der Addition schlägt sich auch in der Geschichte der mechanischen Rechenmaschinen nieder. Bevor in den siebziger Jahren des 20. Jahrhunderts der Taschenrechner seinen Siegeszug antrat, waren preiswerte mechanische Additionshilfen weit verbreitet, während Maschinen, die auch multiplizieren konnten, sehr teuer und langsam waren.
Das nebenstehende Bild zeigt meine erste, vom Taschengeld erworbene Rechenmaschine.

Das Geheimnis dieser Addiatoren war eine Doppelzahnstange (links im Bild blau eingezeichnet), in die ein Stift gesteckt wurde, um die Ziffern zu verschieben. Um z.B. im linken Bild 30 zu addieren, steckt man den Stift in das mit 3 markierte Loch der hervorgehobenen Zehnerstange und zieht in bis zum unteren Ende. Wenn wir aber z.B. 70 addieren möchten, ist das entsprechende Loch rot markiert. Das bedeutet, dass wir nicht nach unten schieben (sonst kämen wir aus dem erlaubten Ziffernbereich heraus, sondern nach oben. Statt 70 zu addieren, subtrahieren wir also 30 (=100-70) und müssen den Fehler korrigieren, indem wir anschließend 100 addieren. Das geht aber in einem Rutsch, indem man oben einfach dem umgebogenen Weg folgt!

Wegen der Unerschwinglichkeit von Multiplikationsmaschinen hat man sich früher beholfen, indem man die Multiplikation mit Hilfe von Logarithmen auf die Addition zurückgeführt hat.

Die folgende Abbildung zeigt das Prinzip:

Statt die Multiplikation x·y direkt durchzuführen, berechnet man die Logarithmen von x und y, addiert diese und wendet auf die Summe die Umkehrfunktion (Exponentialfunktion) an, um das Ergebnis zu erhalten.

In der Praxis wurden deshalb Logarithmentafeln zur Basis 10 gedruckt.
Hier sehen Sie einen Auszug aus einer vierstelligen Logarithmentafel:

0123456789
3004771477347744776477747784780478147834784
3014786478747894790479147934794479647974799
3024800480248034804480648074809481048124813
3034814481648174819482048224823482448264827
3044829483048324833483448364837483948404842
3054843484448464847484948504852485348544856
3064857485948604861486348644866486748694870
3074871487348744876487748784880488148834884
3084886488748884890489148934894489548974898
3094900490149024904490549074908490949114912

Die Hervorhebung steht für 3,024 = 100,4806, aber auch für 30,24 = 101,4806 oder 3024 = 103,4806 usw.

Der Auszug zeigt 100 von 10000 Logarithmen der gesamten Tafel, die etwa 20 Buchseiten benötigt.
Im praktischen Gebrauch waren auch siebenstellige Logarithmentafeln, schon ziemlich dicke Wälzer.

Falls Sie sich fragen, warum man statt Logarithmentafel dann nicht gleich große Multiplikationstafeln gedruckt hat: Eine Logarithmentafel ist eindimensional, zu jeder Zahl (in bestimmten Abständen) enthält sie einen Eintrag. Eine Multiplikationstafel dagegen ist zweidimensional: Sie muss zu jedem Paar von Zahlen einen Eintrag enthalten. So würde aus einem handlichen Buch eine riesige Bibliothek!

Sehr naheliegend ist es auch, die Logarithmen direkt auf Linealen aufzutragen und diese grafisch zu addieren. Einen solchen Rechenschieber hatte bis in die siebziger Jahre hinein praktisch jeder Ingenieur. Um z.B. 2·3 zu berechnen kann man die Logarithen von 2 und 3 addieren, indem man die 2 des unteren Lineals an die 1 (log 1 = 0) des oberen schiebt und nun unter der 3 des oberen Lineals das Ergebnis 6 abliest.

Fortsetzung: Binäre Multiplikation

2. Binäre Multiplikation

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

Eine interessante Variante der schriftlichen Multiplikation entwickeln wir am Beispiel 102·5.
Es gilt:

102   = 2·00    + 0·101   + 1·102
102·5 = 2·100·5 + 0·101·5 + 1·102·5
      = 2·5     + 0·50    + 1·500

Das führt zu folgendem Schema:

 a     b   (a mod 10)·b
───────────────────────
102    5     10
 10   50      0
  1  500    500
───────────────
            510

Wir schreiben also die beiden Faktoren nebeneinander und markieren die letzte Ziffer des ersten Faktors. Diese multiplizieren wir mit dem zweiten Faktor. Das wiederholen wir mit dem ganzzahlig durch 10 dividierten ersten Faktor und dem mit mit 10 multiplizierten zweiten Faktor, bis wir links die letzte Stelle des ersten Faktors haben. Das Multiplikationsergebnis ist die Summe der dritten Spalte.

def Mult10(a, b):
    p = 0
    while a > 0:
        p += (a % 10) * b
        a //= 10
        b *= 10
    return p

print(Mult10(102, 5))    
Natürlich können wir statt der Basis 10 des hier verwendeten Stellenwertsystems eine beliebige andere Basis wählen. Wenn wir 10 durch 2 ersetzen bekommen wir:
def Mult2(a, b):
    p = 0
    while a > 0:
        p += (a % 2) * b
        a //= 2
        b *= 2
    return p

print(Mult2(102, 5))    

Jetzt nutzen wir die Tatsache, dass es im Binärsystem nur zwei Ziffern (0 und 1) gibt und optimieren die gelb unterlegte Zeile. a % 2 ist entweder 0 (dann brauchen wir zu p nichts zu addieren oder 1 (dann müssen wir 1 · b addieren). Damit ergibt sich:

def Mult2(a, b):
    p = 0
    while a > 0:
        if a % 2 == 1:
            p += b
        a //= 2
        b *= 2
    return p

print(Mult2(102, 5))    

Daraus ergibt sich das praktische Verfahren, das u.a. als russische Bauernmultiplikation bekannt ist: Wir halbieren a und verdoppeln b, solange a > 0. Alle b-Werte, bei denen a ungerade ist werden aufaddiert:

 a      b
─────────
102     5
 51    10
 25    20
 12    40
  6    80
  3   160
  1   320
─────────
      510

Dieses Verfahren lässt sich auch sehr elegant implementieren. Da auf dem Computer Zahlen binär dargestellt sind, lassen sich die Verdoppelungen bzw. Halbierungen durch effiziente Verschiebungen um ein Bit nach links bzw. rechts darstellen.

Fortsetzung: Parallele Multiplikation

3. Parallele Multiplikation

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

Fortsetzung: Karatsuba-Multiplikation

4. Karatsuba-Multiplikation

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

Wir lassen nun Python einmal 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?

Aufwand bei der
Karatsuba-
Multiplikation
 

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).
Nein, entscheidend ist, 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!