home

Eine kurze Geschichte der Multiplikation

1. Multiplikation durch Addition

2. Binäre Multiplikation

3. Parallele Multiplikation

4. Karazuba-Multiplikation

2. Binäre 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.

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:

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

Als Beweis der Korrektheit des Algorithmus (Verifikation) folgt eine mit Assertions (Behauptungen) angereicherte Version. Die Richtigkeit der Behauptungen lässt sich schrittweise nachvollziehen.

Aus dem Algorithmus ergibt sich das praktische Verfahren, das u.a. als russische Bauernmultiplikation bekannt ist: Man halbiert a und verdoppelt 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

Den Algorithmus kann man hier gut erkennen, aber in diesem Fall wäre es praktischer, die Faktoren zu vertauschen:

 a      b
─────────
 5    102
 2    204
 1    408
─────────
      510

Dieses Verfahren lässt sich (in maschinennahen Programmmiersprachen) noch effizienter 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. Diese Operatoren gibt es auch in JavaScript (>> und <<). Das ändert aber nichts daran, dass in einer Scriptsprache der Aufruf einer Funktion aufwendiger ist als eine direkte Multiplikation.

Fortsetzung: Parallele Multiplikation

home