Ägyptischen Multiplikationsalgorithmus (Beweis)

[Omikron2]

Hallo Zusammen,

derzeit beschäftige ich mich, im Rahmen eines Schulprojektes, mit dem Ägyptischen Multiplikationsalgorithmus.
Da ich die Vorgehensweise und alle übrigen Formalitäten erledigt habe, würde ich nun gerne versuchen diesen zu beweisen.
Leider weiss ich nicht so wirklich, wie ich anfangen soll.
Hier habe ich ein Zahlenbeispiel verwendet:

http://www.pic-upload.de/view-10204046/Unbenannt.jpg…

Nun hatte ich mir überlegt, eine Fallunterscheidung vorzunehmen, einmal mit b=2k (gerade) und b=2k-1 (ungerade) mit k={1,2,3…}.
Wenn ich das auf die Tabelle anwende, gerate ich allerdings in eine Endlosschleife.
Über eine kleine Hilfestellung würde ich mich sehr freuen.

Mit freundlichen Grüßen

[Viator]

Hi,

das ist sehr interessant, leider bin ich gerade kurz angebunden, werde evtl später aber noch was schreiben können.

Meine erste Idee ist auch eine Fallunterscheidung zu machen, bzw mit Induktion zu kombinieren.

Zuerst zeigen, dass es für w=1,2,… gilt.
w*v=\sum_{i=1}^w v

Dann zeigen, dass diese Halbierungsschritte korrekt sind und somit die Summierung lediglich abkürzen

Viel Erfolg,

peargroup

[Attilius]

Hi

Nun hatte ich mir überlegt, eine Fallunterscheidung
vorzunehmen, einmal mit b=2k (gerade) und b=2k-1 (ungerade)
mit k={1,2,3…}.
Wenn ich das auf die Tabelle anwende, gerate ich allerdings in
eine Endlosschleife.

In eine Endlosschleife kannst du gar nicht geraten. Der Algorithmus terminiert immer (warum?).
Hab mir grade mal eine iterative und eine rekursive Version aufgeschrieben. Schätze zum Beweis wird die rekursive Variante besser geeignet sein. Würde evtl etwas mit Induktion versuchen, aber allerdings grade noch nicht die erleuchtende Idee.

Eingabe: v<sub>0</sub>, w<sub>0</sub>
Ausgabe: v<sub>0</sub>\*w<sub>0</sub>




aegyptisch\_rekursiv := proc(V::integer,W::integer)
 if W=0 then
 return 0;
 fi;
 if W mod 2 = 1 then
 return aegyptisch\_rekursiv(V,W-1)+V;
 else
 return aegyptisch\_rekursiv(2\*V,W/2);
 fi;
end proc:




aegyptisch\_iterativ := proc(v<sub>0</sub>::integer,w<sub>0</sub>::integer)
 u<sub>0</sub> := 0;
 i := 1;
 while w<sub>i</sub>0 do
 if w<sub>i</sub> mod 2 = 1 then
 u<sub>i</sub> := u<sub>i-1</sub> + v<sub>i-1</sub>;
 w<sub>i</sub> := w<sub>i-1</sub> - 1;
 else
 v<sub>i</sub> := v<sub>i-1</sub> \* 2;
 w<sub>i</sub> := w<sub>i-1</sub> / 2;
 fi;
 i := i+1;
 od;
 return u<sub>i</sub>;
end proc:

Vielleicht hilft dir das ja schonmal weiter.
Gruß Sven

[Che_Netzer]

In eine Endlosschleife kannst du gar nicht geraten. Der
Algorithmus terminiert immer (warum?).

Spontan würde mir dazu der Banachsche Fixpunktsatz einfallen, habe aber keine Lust, zu überprüfen, ob das so funktioniert.

mfg,
Ché Netzer

[Thomas_Ramel]

Grüezi Omikron

Da ich die Vorgehensweise und alle übrigen Formalitäten
erledigt habe, würde ich nun gerne versuchen diesen zu
beweisen.

Muss das denn mathematisch erfolgen oder reicht ein ‚einfaches‘ Rechenmodell aus?

Leider weiss ich nicht so wirklich, wie ich anfangen soll.
Über eine kleine Hilfestellung würde ich mich sehr freuen.

Ich habe das Ganze ein einer kleinen Excel-Tabelle mal zusammengefasst und ein wenig automatisiert. Schaust Du dir das Ganze doch mal an - die eingefärbten Zellen sind für die Eingabe der Zahlen gedacht:

http://users.quick-line.ch/ramel/Demo-Daten/Aegyptis…

Mit freundlichen Grüssen

Thomas Ramel

• MVP für MS-Excel -

[Martin]

Hallo,

Nun hatte ich mir überlegt, eine Fallunterscheidung
vorzunehmen, einmal mit b=2k (gerade) und b=2k-1 (ungerade)
mit k={1,2,3…}.

das ist schon mal eine gute Idee Die ÄM ist leicht mit einem Widerspruchbeweis oder (dreimal darfst Du raten…) per vollständiger Induktion verfizierbar.

Die Annahme beim Widerspruchsbeweis ist natürlich, dass die ÄM für irgendwelche Inputs falsche Ergebnisse liefert. Dann wird es etwas tricky: Betrachte die kleinste Inputzahl mit dieser Eigenschaft – irgendeine muss es ja sein. Wie sich schnell zeigen lässt, existiert dann aber stets eine noch kleinere Zahl, bei der die ÄM ebenfalls versagt –> Widerspruch zur Annahme.

Such mal im Internet; es gibt einige PDFs dazu.

Gruß
Martin

[MklMs_764a67]

Hallo,

Ich steige bei der Erklärung nicht so ganz durch, einfacher ist der Algorithmus denke ich auf http://www.planet-schule.de/sf/filme-online.php?film… ab 8:35 erklärt (Geschichte der Mathematik Teil 1). Der zweite Faktor wird einfach im Dualsystem zerlegt und fertig.

Keine Ahnung wie dein Projekt abläuft, aber der ganze Film könnte zum Thema passen und da er in diesem Jahr lief und auf planet-schule zum runterladen zur Verfügung steht darfst du ihn auch im Unterricht komplett zeigen.

hth
MklMs

[Hasenfu]

ÄM ist eigentlich ‚normales‘ Multiplizieren
Hossa

Die Ägyptische Multiplikation (ÄM) ist offensichtlich nichts anderes als unsere „normale“ Multiplikation, wie wir sie alle in der Schule gelernt haben. Jedoch wird sie im Binärsystem durchgeführt. An deinem Beispiel kann man das schön sehen:

Im Binärsystem ist 15₁₀ = 1111₂ und 23₁₀ = 10111₂. Zur Multiplikation schreibt man einfach die Bits der Zahl 15 unter jedes 1-Bit der 23, wobei man sich rechts aufgefüllte 0-Bits denken kann (durch Punkte dargestellt). Die Binärzahlen werden dann addiert.

1111 x 10111
------------
+ 1111
+ 1111.
+ 1111..
+ 11111.... 
------------
= 101011001

Die ÄM realisiert diese Rechnung etwas fummelig im Dezimalsystem.

1) Ist w ungerade?
 \* w ist genau dann ungerade, wenn das rechteste Bit gleich 1 ist.

 2a) Ja, addiere v zum Ergebnis u.
 \* Unter ein 1-Bit von w wird das Bitmuster von w geschrieben.

 2b) Nein, dann tue in diesem Schritt nichts.
 \* Unter ein 0-Bit von w wird nichts geschrieben

3) Verdopple den Wert von v.
 \* Im Binärsystem werden dadurch alle Bits um eine Stelle nach
 \* links verschoben und rechts wird mit einem 0-Bit aufgefüllt.

4) Halbiere den Wert von w und runde gegebenenfalls ab.
 \* Im Binärsystem werden dadurch alle Bits um eine Stelle nach
 \* rechts verschoben. Das bisherige rechteste Bit fällt dabei
 \* am rechten Rand raus.

5) Wenn w ungleich 0 ist, gehe wieder zu Schritt 1.
 \* Solange noch 1-Bits in w vorhanden sind, läuft der Algorithmus.

6) In u steht nun das fertige Ergebnis.
 \* Alle untereinandergeschriebenen Bitmuster sind addiert worden.

Wenn du die Äquivalenz der ÄM mit unserer „normalen“ Schulmultiplikation darstellst, sollte klar sein, dass sie funktioniert. Ist vielleicht besser als ein konkreter mathematischer Beweis, weil man sich dann was darunter vorstellen kann. Solltest du dennoch unbedingt einen mathematischen Beweis geben wollen, schau dir an, wie die Richtigkeit unserer „normalen“ Multiplikation bewiesen wird und übertrage den Beweis ins Binärsystem…

Viele Grüße

Hasenfuß