Quelltext der Seite Ägyptische Multiplikation

Die [[Ägyptische Multiplikation]], auch ''Russische Bauernmultiplikation'' genannt, ist einer der ältesten [[Algorithmus|Algorithmen]] der Welt und dient der Multiplikation zweier Zahlen. Der Algorithmus wurde erstmalig in einem ca. 3500 Jahre alten Papyrus beschrieben<ref>Der 3500 Jahre alte Papyrus ist unsere älteste ''erhaltene'' Quelle. Der Algorithmus ist also vermutlich deutlich älter. </ref> und arbeitet folgendermaßen:

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

== Beispiel ==

Wir wollen das Produkt <math>49 \cdot 271</math> 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
|-
|| <s>24</s> || <s>542</s>
|-
|| <s>12</s> || <s>1084</s>
|-
|| <s>6</s> || <s>2168</s>
|-
|| 3 || 4336
|-
|| 1 || 8672
|}

5. Summiere die übrigen Zahlen in der rechten Spalte

<math>271+4336+8672 = 13279</math>

<math>49 \cdot 271</math> ist also <math>13279</math>.

== Der Algorithmus als PAP ==

Als [[PAP]] dargestellt sieht der Algorithmus folgendermaßen aus:

<mermaid>
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
</mermaid>

[[Kategorie:Algorithmen]]
<references />
{{DEFAULTSORT:Aegyptische_Multiplikation}}