Russische Bauernmultiplikation Rechner
Multiplizieren Sie beliebige zwei Zahlen mithilfe des alten Halbierungs- und Verdopplungsalgorithmus. Sehen Sie jeden Schritt und die binäre Verbindung.
Was ist die russische Bauernmultiplikation?
Die russische Bauernmultiplikation — auch bekannt als ägyptische Multiplikation, äthiopische Multiplikation oder binäre Multiplikation — ist ein alter Algorithmus zum Multiplizieren zweier ganzer Zahlen, der nichts weiter erfordert als die Fähigkeit, eine Zahl zu halbieren, zu verdoppeln und zu addieren. Im Gegensatz zur Standardmultiplikation, die auf auswendig gelernten Einmaleins-Tabellen beruht, reduziert diese Methode jedes Multiplikationsproblem auf eine Abfolge von Halbierungen, Verdopplungen und Additionen.
Die Eleganz des Algorithmus liegt darin, was er offenbart: Er berechnet eigentlich verdeckt eine binäre Multiplikation. Die Zeilen, die Sie behalten (bei denen A ungerade ist), entsprechen genau den Positionen der 1-Bits in der binären Darstellung von A. Das Summieren dieser Zeilen rekonstruiert A×B als eine Summe von Zweierpotenzen mal B — genau die Berechnung, die ein digitaler Computer bei der Hardware-Multiplikation zweier ganzer Zahlen durchführt.
Schritt-für-Schritt: Wie es funktioniert
Um A × B mit der russischen Bauernmethode zu multiplizieren:
- Schreiben Sie A in die linke Spalte und B in die rechte Spalte.
- In jeder neuen Zeile: Halbieren Sie A (verwerfen Sie den Rest) und verdoppeln Sie B.
- Fahren Sie fort, bis A 1 erreicht.
- Streichen Sie jede Zeile durch (als verworfen markieren), in der A gerade ist.
- Addieren Sie alle B-Werte in den Zeilen, in denen A ungerade ist. Diese Summe ist das Produkt A×B.
Beispiel: 7 × 13. Starten Sie mit A=7, B=13. Da 7 ungerade ist, behalten Sie 13. Nächster Schritt: A=3 (⌊7/2⌋), B=26. Da 3 ungerade ist, behalten Sie 26. Nächster Schritt: A=1, B=52. Da 1 ungerade ist, behalten Sie 52. A hat 1 erreicht — stopp. Summe = 13 + 26 + 52 = 91 = 7 × 13. Richtig!
Die binäre Verbindung
Der tiefere Grund, warum der Algorithmus funktioniert, ist, dass jede ganze Zahl A binär geschrieben werden kann: A = b₀ + b₁×2 + b₂×4 + b₃×8 + ... where each bᵢ is 0 or 1. Therefore:
A × B = (b₀×B) + (b₁×2B) + (b₂×4B) + (b₃×8B) + ...
Die Verdopplungsspalte erzeugt B, 2B, 4B, 8B, ... — genau die Terme. Die Halbierungsspalte dividiert A wiederholt durch 2; wann immer der Rest 1 ist (A ist ungerade), ist das entsprechende Bit bᵢ = 1 und der verdoppelte Wert dieser Zeile wird in die Summe einbezogen. Zeilen, in denen A gerade ist, haben bᵢ = 0 und werden verworfen. Der Algorithmus ist daher eine direkte Implementierung der binären Multiplikation, die von Hand durchgeführt wird, ohne Binärzahlen explizit kennen zu müssen.
Zum Beispiel ist 7 im Binärsystem 111₂ = 4+2+1. Also 7×13 = 4×13 + 2×13 + 1×13 = 52 + 26 + 13 = 91. Beachten Sie, dass dies genau die drei behaltenen Zeilen im obigen Algorithmus sind!
Geschichte: Altes Ägypten bis zur modernen Informatik
Die früheste bekannte schriftliche Aufzeichnung dieses Algorithmus findet sich im Papyrus Rhind (auch Ahmes-Papyrus genannt), einem alten ägyptischen Dokument, das auf etwa 1650 v. Chr. datiert wird. Der Papyrus zeigt ägyptische Schreiber, die Multiplikationsprobleme ausschließlich durch Verdoppeln lösten — sie verdoppelten eine Zahl wiederholt und wählten dann die entsprechenden Verdopplungen aus, um ein Zielprodukt zu summieren.
Dieselbe Technik wurde unabhängig entdeckt oder nach Äthiopien übertragen (wo sie in einigen Regionen immer noch als äthiopische Multiplikation bezeichnet wird) und später nach Russland, wo sie Berichten zufolge noch im frühen 20. Jahrhundert von Bauern und Händlern verwendet wurde — Menschen, die multiplizieren mussten, aber keine formellen Einmaleins-Tabellen gelernt hatten. Charles Peirce, der amerikanische Logiker, beschrieb die Methode im 19. Jahrhundert und erkannte ihre logische Schönheit.
Im Computerzeitalter erlangte der Algorithmus als theoretische Grundlage für Hardware-Multiplikatoren wieder an Bedeutung. Jede moderne CPU verwendet Shift-and-Add-Schaltkreise, die genau diesen Algorithmus implementieren: Das Verschieben nach links multipliziert mit 2 (Verdoppeln), das Verschieben nach rechts dividiert durch 2 (Halbieren), und die bedingte Akkumulation verarbeitet die Summe der behaltenen Zeilen.
Vergleich mit Standardmultiplikation
| Aspekt | Russischer Bauer | Standard (Lange) Multiplikation |
|---|---|---|
| Voraussetzungen | Nur Halbieren, Verdoppeln, Addieren | Einmaleins 0–9 auswendig gelernt |
| Schritte für n-stellige Zahlen | O(log₂ A) Halbierungen + Additionen | O(n²) Ziffernmultiplikationen |
| Fehleranfälligkeit | Einfach jeden Schritt zu überprüfen | Fehler beim Erinnern an das Einmaleins möglich |
| Pädagogischer Wert | Offenbart die binäre Struktur von Zahlen | Baut das Verständnis für Stellenwerte auf |
| Computeranalogie | Lässt sich direkt auf Shift-and-Add abbilden | Erfordert Ziffern-Nachschlagetabellen |
Anwendungen in der Informatik
Der russische Bauernalgorithmus inspirierte direkt mehrere wichtige Bereiche der Informatik. Hardware-Multiplikatoren in CPUs verwenden eine Variante namens Shift-and-Add-Multiplikation, bei der ein Links-Shift eine Zahl verdoppelt (entsprechend der Verdopplungsspalte) und das Testen des niedrigstwertigen Bits ungerade Zahlen identifiziert (entsprechend der Überprüfung der Halbierungsspalte). Dies macht die Multiplikation zu O(log n) Operationen in Bezug auf die Anzahl der Bits.
Schnelle Exponentiation (auch Exponentiation durch Quadrieren genannt) wendet dieselbe Idee auf Potenzen an: compute aⁿ by repeatedly squaring and selecting which squares to multiply together based on the binary representation of n. This is fundamental to RSA cryptography, where modular exponentiation with 2048-bit exponents must be computed efficiently. The Russian Peasant multiplication algorithm, thousands of years old, is thus at the heart of every secure HTTPS connection you make today.