Ergänzungen zur ägyptischen Multiplikation

Auf der Seite 4 des Büchleins wird die ägyptische Multiplikation besprochen. Natürlich geht der Beweis, dass das ägyptische Verfahren richtig ist, auch ,,von unten``.

Sei

$$\mathbb {T}$$ = {b| a ^. k = aemul (a, k) für allek$$\le$$b}

Es ist 0 $\in$ $\mathbb {T}$. Sei b $\in$ $\mathbb {T}$. Wir betrachten b + 1.

1.Fall: b + 1 = 2 ^. s ist gerade. Dann ist s = (b + 1)/2$\le$b. Daher ist aemul (a, b) = aemul (a, 2 ^. s) = aemul (a ^. 2, s) = (a ^. 2)s = a ^. (2s) = a ^. (b + 1).

2. Fall: b + 1 ist ungerade. Dann ist aemul (a, b + 1) = aemul (a, b) + a = a ^. b + a = a(b + 1). Also gehört in jedem Fall b + 1 zu $\mathbb {T}$. Es ist daher $\mathbb {T}$ induktiv und somit gleich $\mbox{$\mathbb{N}$}$.

Die ägyptische Multiplikation soll in Lisp programmiert werden.

Die Funktion ergibt t, wenn x gerade ist, andernfalls nil. Entsprechend gibt diese Funktion t, wenn x ungerade ist.

  (defun aemulr(a b)
   (if (= b 0) 0
       (if (= (mod b 2) 0) (aemulr (* a 2) (/ b 2))
                      (+ (aemulr a (- b 1)) a))))
(aemulr 33 1234) ===> 40722

Die Funktion ist rekursiv definiert, die Definition ist genau dem Beweis aus dem Büchlein nachvollzogen.

1. Ist b = 0, so wird 0 zurückgegeben.
2. Ist b gerade, so wird die Funktion aemulr mit den Argumenten a ^. 2 und b/2 aufgerufen.
3. Ist b ungerade, so wird die Funktion mit den Argumenten a, b - 1 aufgerufen und a dazu addiert. Also a + aemul (a, b - 1).

Diese Art der Programmierung kann wörtlich für Common Lisp übernommen werden. Die Multiplikation von a mit 2 kann durch a + a ersetzt werden.

Verfolgt man, wie die verschiedenen Aufrufe in die Tiefe gehen, versteht man vielleicht besser wie die Funktion arbeitet.

(aemulr 67 3)

1 -> aemulr: a=67 b=3
| 2 -> aemulr: a=67 b=2
| | 3 -> aemulr: a=134 b=1
| | | 4 -> aemulr: a=134 b=0
| | | 4 <- aemulr: 0
| | 3 <- aemulr: 134
| 2 <- aemulr: 134
1 <- aemulr: 201

Ich möchte dies genau erklären:

1. Die Funktion wird aufgerufen mit den Argumenten a = 67 und b = 3.

2. Da b $\neq$ 0 ist, und b ist wird aemulr mit den Argumenten 67 und 2 aufgerufen. Auf dieser zweiten Stufe wird sich a = 67 zum Addieren gemerkt. Wir erhalten den Term 67 + aemul (67, 2).
3. Wieder ist b $\neq$ 0 und infolgedessen wird die Funktion zum dritten Mal aufgerufen. Diesmal weil b gerade ist mit den Argumenten 134 und 1. Wir erhalten den Term 67 + aemul (134, 1).
4. Das zweite Argument ist wieder ungerade. Also wird die Funktion auf der 4ten Stufe wieder aufgerufen mit den Argumenten a = 134 und b = 0. Wir erhalten den Term 67 + 134 + aemul (134, 0).
5. Im 5ten Aufruf ist b = 0. Es wird das erste Argument 0 auf die 4te Stufe zurückgegeben. Da sich dort 134 gemerkt wurde wird zu 0 die 134 dazu addiert und das Ergebnis auf die 3te Stufe nach oben durchgereicht. Dort wurde sich nichts gemerkt. Also einfach auf die 2te Stufe. Dort liegt 67 zum Addieren bereit.
6. Auf der ersten Stufe wird dann 201 ausgegeben.

Dies Verfahren ist nicht ganz einfach zu verstehen. Man sollte es sich durch Listen nochmal klarer machen.

Zu den Beispielen im Buch: (aemulr 32 31) 992

(aemulr 31 32) 992 (aemulr 17 17) 289

(aemulr 111 1231) 136641 (aemulr 3 63) 189 (aemulr 3 7)

1 -> aemulr: a=3 b=7
| 2 -> aemulr: a=3 b=6
| | 3 -> aemulr: a=6 b=3
| | | 4 -> aemulr: a=6 b=2
| | | | 5 -> aemulr: a=12 b=1
| | | | | 6 -> aemulr: a=12 b=0
| | | | | 6 <- aemulr: 0
| | | | 5 <- aemulr: 12
| | | 4 <- aemulr: 12
| | 3 <- aemulr: 18
| 2 <- aemulr: 18
1 <- aemulr: 21

Aber (aemulr 7 3)

1 -> aemulr: a=7 b=3
| 2 -> aemulr: a=7 b=2
| | 3 -> aemulr: a=14 b=1
| | | 4 -> aemulr: a=14 b=0
| | | 4 <- aemulr: 0
| | 3 <- aemulr: 14
| 2 <- aemulr: 14
1 <- aemulr: 21

Man sieht daher, dass der Aufwand keineswegs kommutativ ist.

Bei diesem Verfahren ist es unschön, dass beim Aufsteigen weiter gerechnet werden muss. Besser wäre es, wenn man schon auf der untersten Stufe das Ergebnis hätte. Es könnte unverändert nach oben durchgereicht werden. Man nennt dies endrekursiv.

Eine bessere Verwirklichung dieser Art der Multiplikation ist daher:

1 -> russ: p=0 a=33 b=5
| 2 -> russ: p=33 a=33 b=4
| | 3 -> russ: p=33 a=66 b=2
| | | 4 -> russ: p=33 a=132 b=1
| | | | 5 -> russ: p=165 a=132 b=0
| | | | 5 <- russ: 165
| | | 4 <- russ: 165
| | 3 <- russ: 165
| 2 <- russ: 165
1 <- russ: 165

(defun russ(p a b)
    (if (= b 0) p
    (if (= (mod b 2) 0) (russ p (+ a a) (/ b 2))
        (russ (+ p a) a (1- b))
        )))

Wir sehen: Hier ist das Ergebnis auf der tiefsten Stufe ausgerechnet. Es braucht nur noch nach oben durchgereicht werden.

Aufgaben:

1. Eine Funktion ae : $\mbox{$\mathbb{N}$}$×$\mbox{$\mathbb{N}$}$ $\rightarrow$ $\mbox{$\mathbb{N}$}$ wird folgendermaßen definiert:
   • ae(a, 0) = p mit festem p $\in$ $\mbox{$\mathbb{N}$}$ für alle a $\in$ $\mbox{$\mathbb{N}$}$.
   • Ist b gerade, so ist ae(a, b) = ae(a + a, b/2).
   • Ist b ungerade so ist ae(a, b) = a + ae(a, b - 1).
   Gebe einen Term für ae(a, b) für alle a, b $\in$ $\mbox{$\mathbb{N}$}$ an. Beweise, dass dieser Term tatsächlich die Funktion ae(a, b) beschreibt.
2. Eine Funktion f : $\mbox{$\mathbb{N}$}$×$\mbox{$\mathbb{N}$}$ $\rightarrow$ $\mbox{$\mathbb{N}$}$ heiße ägyptisch, wenn sie die folgenden zwei Eigenschaften hat:
   • f (a, b)) = f (a + a, b/2), falls b gerade ist.
   • f (a, b) = a + f (a, b - 1) falls b ungerade ist.
   1. Gibt es eine kommutative ägyptische Abbildung f : $\mbox{$\mathbb{N}$}$×$\mbox{$\mathbb{N}$}$ $\rightarrow$ $\mbox{$\mathbb{N}$}$ mit f (1, 0) = 1 und f (3, 0) = 2?
   2. Zeige Ist f ägyptisch, so ist für alle n $\in$ $\mbox{$\mathbb{N}$}$: f (0, n) = f (0, 0).
   3. Kennzeichne alle kommutative ägyptischen Abbildungen f$\mbox{$\mathbb{N}$}$×$\mbox{$\mathbb{N}$}$ $\rightarrow$ $\mbox{$\mathbb{N}$}$.
   4. Kennzeichne alle ägyptischen Funktionen f : $\mbox{$\mathbb{N}$}$×$\mbox{$\mathbb{N}$}$ $\rightarrow$ $\mbox{$\mathbb{N}$}$. Ich weiß keine Antwort
   5. Kennzeichne alle ägyptischen Funktionen $\mbox{$\mathbb{R}$}$×$\mbox{$\mathbb{N}$}$ $\rightarrow$ $\mbox{$\mathbb{R}$}$. Auch hier weiß ich keine Antwort.

3. Wir wollen den Begriff verallgemeinern: Sei M eine beliebige nicht leere Menge. und o: M×M $\rightarrow$ M eine Funktion. Wir wollen das Zeichen o zwischen die Argumente schreiben. Also anstelle o(a, b) = aob Eine Funktion f : M×$\mbox{$\mathbb{N}$}$ $\rightarrow$ M heißt ägyptisch, wenn gilt:
   • f (m, b) = f (mom, b/2) für alle m $\in$ M und alle geraden b $\in$ $\mbox{$\mathbb{N}$}$.
   • f (m, b) = f (m, b - 1)om für alle ungeraden b $\in$ $\mbox{$\mathbb{N}$}$.
   1. Was ergibt sich, wenn man die Menge M = $\mbox{$\mathbb{N}$}$ wählt und als Verknüpfung o die Multiplikation?
   2. Es sei M = $\mbox{$\mathbb{R}$}$ und o: $\mbox{$\mathbb{R}$}$×$\mbox{$\mathbb{R}$}$ $\ni$ (a, b) $\mapsto$ $\sqrt{{a^{2}+b^{2}}}$ $\in$ $\mbox{$\mathbb{R}$}$.
   3. Es sei M = $\mbox{$\mathbb{R}$}$ und o: $\mbox{$\mathbb{R}$}$×$\mbox{$\mathbb{R}$}$ $\ni$ (a, b) $\mapsto$ (a + b)/2 $\in$ $\mbox{$\mathbb{R}$}$. Was ergibt sich?
   4. Wähle M = $\mbox{$\mathbb{N}$}$ und o: $\mbox{$\mathbb{N}$}$×$\mbox{$\mathbb{N}$}$ $\ni$ (a, b) $\mapsto$ a^b $\in$ $\mbox{$\mathbb{N}$}$.
      1. Es sei f (a, 0) = 1 für alle a. Berechne f (3, 6).
      2. Berechne f (5, 5).

Lösungen:

1

Behauptung: Für alle a, b $\in$ $\mbox{$\mathbb{N}$}$ ist ae(a, b) = p + a ^. b.

Beweis: Es ist für alle a ae(a, 0) = p = p + a ^. 0. Für b = 1 und beliebiges a erhält man ae(a, 1) = a + ae(a, 0) = a + p = p + a ^. 1. Es sei

$$\in \mbox{$\mathbb{N}$} \le$$

Wir haben gerade nachgerechnet, dass 0 und 1 in T sind. Sei b $\in$ T. Wir betrachten nun b + 1.

1. Fall: b + 1 = 2 ^. s ist gerade. Dann ist ae(a, 2s) = ae(a ^. 2, s) = p + a ^. 2 ^. s = p + a ^. (b + 1).

2. Fall: b + 1 ist ungerade. ae(a, b + 1) = a + ae(a, b) = a + p + a ^. b = p + a ^. (b + 1) Daher ist T induktiv und die Behauptung folgt für alle b.

2

2a

Antwort: Nein. Denn Angenommen f ist eine solche kommutative ägyptische Abbildung. Dann ist insbesonders f (0, 3) = 0 + f (0, 2) = f (0, 1) = 0 + f (1, 0) = 1. Andererseits sollte f (3, 0) = 2 sein. Dies widerspricht sich. Ich weiß noch nicht ob es überhaupt solche ägyptischen Abbildungen gibt