Russische Bauernmultiplikation – einfach erklärt

Grundidee und Ablauf

Die Russische Bauernmultiplikation ist ein einfaches Verfahren zur Multiplikation zweier natürlicher Zahlen. Sie benötigt im Wesentlichen nur Halbieren, Verdoppeln und Addieren; das kleine Einmaleins ist nicht erforderlich. Im Hintergrund wird eine schriftliche Multiplikation im Binärsystem durchgeführt. Eine entsprechende Methode war bereits im alten Ägypten bekannt und ist auf dem Papyrus Rhind beschrieben.

Vorgehen:

Die beiden Zahlen werden nebeneinandergeschrieben. Die linke Zahl ist der Multiplikator, die rechte der Multiplikand.
Der Multiplikator wird wiederholt halbiert. Reste werden stets abgerundet. Die Ergebnisse werden untereinander notiert, bis die Zahl 1 erreicht ist.
Der Multiplikand wird gleichzeitig jeweils verdoppelt.
Steht links eine gerade Zahl, wird die zugehörige Zahl rechts gestrichen; bei einem geraden ursprünglichen Multiplikator betrifft dies auch den Multiplikanden selbst.
Die Summe des nicht gestrichenen Multiplikanden und seiner nicht gestrichenen Verdoppelungen ist das gesuchte Produkt.

Für einen kürzeren Rechenweg verwendet man möglichst die kleinere der beiden Zahlen als Multiplikator, weil dann schneller die 1 erreicht wird.

Beispiel: 27 mal 82

Das Produkt aus 27 und 82 wird so berechnet:

27 | 82 → 82 wird addiert
13 | 164 → 164 wird addiert
6 | 328 → gestrichen, weil 6 gerade ist
3 | 656 → 656 wird addiert
1 | 1312 → 1312 wird addiert

Die nicht gestrichenen Werte ergeben:

82 + 164 + 656 + 1312 = 2214.

Damit gilt 27 × 82 = 2214. In der im Artikel angegebenen Binärdarstellung lauten die Ausgangszahlen 27 = 11011 und 82 = 1010010; das Produkt 2214 wird als 100010100110 dargestellt.

Erklärung und Optimierung

Die Methode beruht auf der Zerlegung des Multiplikators in Zweierpotenzen:

82 × 27 = 82 × (2^0 + 2^1 + 0 × 2^2 + 2^3 + 2^4) = 82 × 2^0 + 82 × 2^1 + 82 × 0 + 82 × 2^3 + 82 × 2^4 = 82 + 164 + 0 + 656 + 1312 = 2214.

Die Summanden mit dem Faktor 0 entsprechen den gestrichenen Zeilen. In der Binärdarstellung erkennt man eine gerade Zahl daran, dass ihr niederwertigstes Bit, also die ganz rechte Stelle, 0 ist.

Das Verfahren kann auch auf Produkte rationaler Zahlen angewendet werden; dies war laut Artikel ebenfalls bereits den Ägyptern bekannt. Um möglichst wenige Halbierungen beziehungsweise Divisionsschritte auszuführen, kann man die Faktoren vertauschen. Um die Zahl der Additionen zu verringern, ist es günstig, die Zahlen so zu vertauschen, dass der gerade Faktor halbiert wird. Die Korrektheit des Verfahrens lässt sich durch vollständige Induktion beweisen.

Frühe Computer und binäre Exponentiation

Frühe CPUs konnten in ihrer arithmetisch-logischen Einheit meist addieren und subtrahieren, aber normalerweise nicht multiplizieren. Die Bauernmultiplikation ließ sich deshalb als kleine Schleife aus Additionen, bitweisen Verschiebungen und Bit-Tests umsetzen und wurde häufig für Ad-hoc-Multiplikationen verwendet.

Dieselbe Grundidee dient auch zur Berechnung von Potenzen mit großen ganzzahligen Exponenten. Bei der binären Exponentiation wird der Exponent schrittweise halbiert, während die Basis quadriert wird. Am Ende werden die Potenzen mit ungeraden Exponenten miteinander multipliziert.