Ägyptische Multiplikation

Die Ägyptische Multiplikation, auch Russische Bauernmultiplikation genannt, ist einer der ältesten Algorithmen der Welt und dient der Multiplikation zweier Zahlen. Der Algorithmus wurde erstmalig in einem ca. 3500 Jahre alten Papyrus beschrieben und arbeitet folgendermaßen:

1. Schreibe die beiden Faktoren nebeneinander.
2. Auf der linken Seite werden die Zahlen jeweils halbiert, abgerundet und untereinander geschrieben, bis man bei der 1 ankommt
3. Auf der rechten Seite werden die Zahlen jeweils verdoppelt und ebenfalls untereinander geschrieben
4. Nun werden die Zahlen zeilenweise durchgegangen und die Zeilen gestrichen, in denen links eine gerade Zahl steht
5. Von allen übrigen Zeilen werden die rechten Zahlen aufaddiert und ergeben das Produkt

Beispiel

Wir wollen das Produkt $49\cdot 271$ berechnen.

1. Schreibe die Faktoren nebeneinander

49

271

2. Halbiere die linke Seite bis zur 1

49	271
24
12
6
3
1

3. Verdoppele jeweils die rechte Seite

49	271
24	542
12	1084
6	2168
3	4336
1	8672

4. Streiche die Zeilen, in denen links gerade Werte stehen

49	271
24	542
12	1084
6	2168
3	4336
1	8672

5. Summiere die übrigen Zahlen in der rechten Spalte

$271+4336+8672=13279$

$49\cdot 271$ ist also $13279$.

Der Algorithmus als PAP

Als PAP dargestellt sieht der Algorithmus folgendermaßen aus:

graph TD start(("Start")) --> ina[/"a := Eingabe"/] --> inb[/"b := Eingabe"/] --> initprod["p := 0"] --> while{"a ≥ 1?"} -- ja --> if{"a ist gerade?"} -- nein --> add["p := p + b"] --> div["a := a / 2, abgerundet"] --> mul["b := b · 2"] --> while -- nein --> out[/"Ausgabe p"/] --> ende(("Ende")) if -- ja --> div