Russische Bauernmultiplikation
Die Russische Bauernmultiplikation ist ein einfaches Verfahren zur Multiplikation zweier natürlicher Zahlen.Es war schon im Altertum bekannt, in Deutschland wurde es bis ins Mittelalter verwendet. In Russland war es bis weit in die Neuzeit üblich, daher der Name.
Das Verfahren hat den Vorteil, dass man im Prinzip nur halbieren, verdoppeln und addieren können muss, das kleine Einmaleins wird nicht benötigt. Implizit wird eine schriftliche Multiplikation im Binärsystem durchgeführt.
Und so funktioniert das Verfahren:
- Man schreibt die beiden zu multiplizierenden Zahlen nebeneinander.
- Auf der linken Seite werden die Zahlen jeweils halbiert (Reste abgerundet) und die Ergebnisse untereinander geschrieben, bis man zur 1 gelangt.
- Auf der rechten Seite werden die Zahlen verdoppelt und untereinander geschrieben.
- Die rechts stehenden (verdoppelten) Zahlen werden gestrichen, wenn die links stehende Zahl gerade ist.
- Die Summe der nicht gestrichenen rechts stehenden Zahlen ergibt das gesuchte Produkt.
Beispiele
35 * 89 | 84 * 123 | |||
35 | 89 | 84 | ||
17 | 178 | 42 | ||
8 | 21 | 492 | ||
4 | 10 | |||
2 | 5 | 1968 | ||
1 | 2848 | 2 | ||
Ergebnis | 3115 | 1 | 7872 | |
Ergebnis | 10332 |
Dieselbe Idee kann auch benutzt werden, um Potenzen mit großen ganzzahligen Exponenten zu berechnen. Dazu schreibt man den Exponenten links und die Basis rechts. Der Exponent wird schrittweise halbiert und die Basis schrittweise quadriert. Man streicht die Zeilen mit geradem Exponenten. Das Produkt der nichtgestrichenen rechten Zahlen ist die gesuchte Potenz.
Analoges Verfahren: Schnelles Potenzieren
218 | |
18 | |
9 | 4 |
4 | |
2 | |
1 | 65536 |
Ergebnis | 262144 |
Große Exponenten treten vor allem dann auf, wenn man modulo einer natürlichen Zahl rechnet. Für diesen Fall ist eine leichte Modifikation anwendbar: Man bildet nach jedem Quadrieren den Rest:
218 mod 39 | |
18 | |
9 | 4 |
4 | |
2 | |
1 | 16 (= 484 mod 39) |
Ergebnis | 25 (= 4·16 mod 39) |