Verdoppeln und Halbieren

Die Multiplikation

Für die Multiplikation zweier natürlicher Zahlen kann auch das folgende − bereits im alten Ägypten angewendete und im folgenden anhand der Multiplikation 45 ⋅ 67 vorgestellte − Verfahren, das genau genommen nur die Kenntnis des Halbierens, Verdoppelns und Addierens voraussetzt, durchgeführt werden:

45	67	Zu Beginn werden beide Faktoren in zwei nebeneinander liegende Spalten geschrieben.
45 22 11 5 2 1	67 134 268 536 1072 2144	Nun wird der erste Faktor in der ersten Spalte Zeile für Zeile solange durch 2 dividiert, bis als Ergebnis die Zahl 1 auftritt. Dabei werden etwaige nichtganzzahlige Ergebnisse auf die nächstliegende ganze Zahl abgerundet und danach die Division durch 2 fortgeführt. Parallel zum Halbieren des ersten Faktors in der ersten Spalte wird der Faktor der zweiten Spalte fortlaufend verdoppelt.
45 22 11 5 2 1	67 134 268 536 1072 2144	Jetzt werden alle Zeilen, die in der linken Spalte eine gerade Zahl enthalten, gestrichen.
45 22 11 5 2 1	67 134 268 536 1072 2144 3015	Abschließend werden alle nicht gestrichenen Zahlen der zweiten Spalte addiert. Die dadurch gebildete Summe ist das gesuchte Produkt der beiden Faktoren.

Das scheinbar Kuriose an diesem Verfahren ist, daß die Rechnung trotz etwaiger Rundungen in der ersten Spalte stets das richtige Ergebnis liefert.

Warum funktioniert also dieses Verfahren ?

Die Richtigkeit des Verfahrens kann mit der binären Darstellung des ersten Faktors begründet werden.
Nimmt man als Beispiel die oben zitierte Multiplikation 45 ⋅ 67, so gilt für den ersten Faktor bekanntlich 45 = 32 + 8 + 4 + 1, da die binäre Darstellung der dezimalen Zahl 45 gerade 101101 lautet.
Es gilt daher für die Multiplikation 45.67:

45 ⋅ 67 = (32 + 8 + 4 + 1) ⋅ 67 = 32 ⋅ 67 + 8 ⋅ 67 + 4 ⋅ 67 + 1 ⋅ 67

Das gesuchte Produkt kann also durch Addieren jener Zahlen aus der Spalte der Verdoppelungen, bei denen die Binärstelle des ersten Faktors gerade 1 ist, gebildet werden.

Somit stellt sich die Frage nach einer möglichst praktischen Umwandlung des ersten Faktors in das binäre Zahlensystem.

Betrachtet man die Einträge der ersten Spalte des Beispieles 45 ⋅ 67 sowohl in dezimaler als auch in dualer Form, so erhält man folgende Gegenüberstellung:

dezimal	dual
45	101101
22	10110
11	1011
5	101
2	10
1	1

Liest man diese Tabelle "von unten nach oben", so ergibt sich:

dezimal	dual
1	1
2	10
5	101
11	1011
22	10110
45	101101

Aus dem Dezimalsystem ist bekannt, daß das Verschieben aller Stellen einer Dezimalzahl um eine Stelle nach links und das anschließende Setzen der Ziffer 0 an die (neue) Einerstelle einer Multiplikation mit dem Faktor 10 entspricht.
Auch im Dualsystem können diese Schritte durchgeführt werden, allerdings wird die duale Zahl nicht mit dem Faktor 10, sondern mit dem Faktor 2 multipliziert.
Man erhält also aus der dualen Zahl 1 (dezimal 1) durch Verdoppeln die duale Zahl 10 (dezimal 2).
Wird nun diese Zahl verdoppelt und anschließend um eine Einheit vermehrt, so erhält man im Dualsystem über den Zwischenschritt 100 (dezimal 4) das Ergebnis 101 (dezimal 5).
Für die Ermittlung der binären Darstellung der dezimalen Zahl 45 muß daher die soeben angeführte Gegenüberstellung "von unten nach oben" gelesen werden, d.h. man berechnet zuerst die duale Einerstelle des ersten Faktors:

dezimal	dual
45	...cba1

Die duale (noch unbekannte) Zifferngruppe ...cba entspricht der dezimalen Zahl 44 (45 − 1).
Nun wird die Einerstelle (1) der dualen Zifferngruppe ...cba1 entfernt und jede der noch unbekannten Ziffern ...cba um eine Stelle nach rechts verschoben. Da dies im Dualsystem einer Halbierung (genauer: Teilung durch die Basis 2) entspricht, muß auch die entsprechende Dezimalzahl durch 2 geteilt werden.
Damit ergibt sich als Zwischenergebnis:

dezimal	dual
45	...cba1
22	...cba

Die dezimale Zahl 22 ist bekanntlich eine gerade Zahl, weshalb sie im Dualsystem die Einerstelle 0 besitzt.
Somit gilt:

dezimal	dual
45	...cba1
22	...cb0

Wird nun wiederum die Einerstelle der aktuellen dualen Zifferngruppe ...cb0 entfernt und jede der noch unbekannten Ziffern um eine Stelle nach rechts verschoben, so erhält man

dezimal	dual
45	...cba1
22	...cb0
11	...cb

Bei weiterer Fortführung des Verfahrens erhält man die bereits angeführte Tabelle

dezimal	dual
45	101101
22	10110
11	1011
5	101
2	10
1	1

Fazit:

Wenn die jeweilige Hälfte der Dezimalzahl eine ungerade Zahl ist, so entsteht an der entsprechenden Binärstelle des ersten Faktors die Ziffer 1.
Und da für das gesuchte Produkt genau jene Zeilen der "Verdoppelungsspalte" benötigt werden, bei denen die Binärstelle des ersten Faktors 1 ist, werden nur jene Zeilen aus der "Verdoppelungsspalte" addiert, bei denen die Zahlen aus der "Halbierungsspalte" ungerade sind.