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·100 + 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 effizient implementieren. Da auf dem Computer Zahlen binär dargestellt sind, lassen sich die Verdoppelungen bzw. Halbierungen durch Verschiebungen um ein Bit nach links bzw. rechts darstellen, die jeder Prozessor sehr schnell ausführen kann.
Fortsetzung: Parallele Multiplikation