Ägyptische Multiplikation: Unterschied zwischen den Versionen

Aus KGS-Wiki
(Artikel begonnen)
 
 
(3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 12: Zeile 12:


1. Schreibe die Faktoren nebeneinander
1. Schreibe die Faktoren nebeneinander
{|
{|
|| <math>49</math> || <math>271</math>
|| 49 || 271
|}
|}


2. Halbiere die linke Seite bis zur 1
2. Halbiere die linke Seite bis zur 1
{|
{|
|| <math>49</math> || <math>271</math>
|| 49 || 271
|-
|-
|| <math>24</math> ||
|| 24 ||
|-
|-
|| <math>12</math> ||
|| 12 ||
|-
|-
|| <math>6</math> ||
|| 6 ||
|-
|-
|| <math>3</math> ||  
|| 3 ||  
|-
|-
|| <math>1</math> ||
|| 1 ||
|}
|}


3. Verdoppele jeweils die rechte Seite
3. Verdoppele jeweils die rechte Seite
{|
{|
|| <math>49</math> || <math>271</math>
|| 49 || 271
|-
|-
|| <math>24</math> || <math>542</math>
|| 24 || 542
|-
|-
|| <math>12</math> || <math>1084</math>
|| 12 || 1084
|-
|-
|| <math>6</math> || <math>2168</math>
|| 6 || 2168
|-
|-
|| <math>3</math> || <math>4336</math>
|| 3 || 4336
|-
|-
|| <math>1</math> || <math>8672</math>
|| 1 || 8672
|}
|}


4. Streiche die Zeilen, in denen links gerade Werte stehen
4. Streiche die Zeilen, in denen links gerade Werte stehen
{|
{|
|| <math>49</math> || <math>271</math>
|| 49 || 271
|-
|-
|| <math>24</math> || <math>542</math>
|| <s>24</s> || <s>542</s>
|-
|-
|| <math>12</math> || <math>1084</math>
|| <s>12</s> || <s>1084</s>
|-
|-
|| <math>6</math> || <math>2168</math>
|| <s>6</s> || <s>2168</s>
|-
|-
|| <math>3</math> || <math>4336</math>
|| 3 || 4336
|-
|-
|| <math>1</math> || <math>8672</math>
|| 1 || 8672
|}
|}


{{Lückenhaft}}
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}}

Aktuelle Version vom 22. April 2024, 12:58 Uhr

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[1] 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 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

ist also .

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

  1. ↑ Der 3500 Jahre alte Papyrus ist unsere älteste erhaltene Quelle. Der Algorithmus ist also vermutlich deutlich älter.
Abgerufen von „https://wiki.kah.gs/index.php?title=Ägyptische_Multiplikation&oldid=4291“