Tutoriums-Aufgabe Ägyptische Multiplikation – edit

Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet. Lorem ipsum dolor sit amet, consetetur sadipscing elitr, sed diam nonumy eirmod tempor invidunt ut labore et dolore magna aliquyam erat, sed diam voluptua. At vero eos et accusam et justo duo dolores et ea rebum. Stet clita kasd gubergren, no sea takimata sanctus est Lorem ipsum dolor sit amet.

Überschrift 2

Überschrift 3

| zahl1 | zahl2 | produkt |
|:-----:|:-----:|:-------:|
| 11| 23| 0|
| 5| 46| 23|
| 2| 92| 69|
| 1| 184| 69|
| 0| 368| 253|
$ a^2 = b^2 $

Tutoriums-Aufgabe "Ägyptische Multiplikation" (überarbeitet)

Niklas Graupner


(a) Teste das Verfahren mit der Multiplikationsaufgabe $11 \cdot 23 = ...$ Überprüfe den zugehörigen Algorithmus mit einer Trace-Tabelle.

zahl1 zahl2 produkt
11 23 0
5 46 23
2 92 69
1 184 69
0 368 253

Das Ergebnis der ägyptischen Multiplikation ist in der letzten Zelle von produkt zu sehen: $11 \cdot 23 = 253$.


(b) Hier eine Implementierung zum Verfahren. Teste, ob sich das Programm so verhält wie gewünscht.

# Eingabe
zahl1 = int(input("Zahl 1: "))
zahl2 = int(input("Zahl 2: "))

# Verarbeitung
produkt = 0
while zahl1 > 0:
    if zahl1 % 2 == 1:
        produkt = produkt + zahl2
    zahl1 = zahl1 / 2
    zahl2 = zahl2 * 2

# Ausgabe
print("Produkt: ", produkt)

Nein, das Programm gibt falsche Ergebnisse aus.


(c) Das Programm liefert merkwürdige Ausgaben. Suche den Fehler mit zusätzlichen Ausgabeanweisungen. Korrigiere den Fehler und teste das Programm erneut.

Wenn das Programm mit zusätzlichen print-Statements versehen wird, sieht es wie folgt aus.

# Quelltext mit zusätzlichen print-statements
# Eingabe
zahl1 = int(input("Zahl 1: "))
zahl2 = int(input("Zahl 2: "))

# Verarbeitung
produkt = 0
while zahl1 > 0:
    print("Iteration mit", zahl1) # <---------------NEU
    if zahl1 % 2 == 1:
        print(zahl1, "ist ungerade ungerade") # <---NEU
        produkt = produkt + zahl2
        print("neues Produkt", produkt) # <---------NEU
    zahl1 = zahl1 / 2
    print("neue zahl1:", zahl1) # <-----------------NEU
    zahl2 = zahl2 * 2
    print("neue zahl2:", zahl2) # <-----------------NEU

# Ausgabe
print("Produkt: ", produkt)

Hier ein Ausschnitt aus der Ausgabe:

    (...)
    Iteration mit 1e-323
    neue zahl1: 5e-324
    neue zahl2: 3238436052916969893639925547502676912792906396226273893710421728438885433087925550271366139222993991922993245829068990582236939798172695629872214399051816158744278788425061781831470523873491461459836282855563921096992119734795083177889653690386552901452960904197740312837334633843688040514981240138336100212923323857495916544
    Iteration mit 5e-324
    neue zahl1: 0.0
    neue zahl2: 6476872105833939787279851095005353825585812792452547787420843456877770866175851100542732278445987983845986491658137981164473879596345391259744428798103632317488557576850123563662941047746982922919672565711127842193984239469590166355779307380773105802905921808395480625674669267687376081029962480276672200425846647714991833088
    Produkt:  4

Infinite loop / Endlosschleife

Die Variablen zahl1 und zahl2 befinden sich in einer Endlosschleife (while zahl1 > 0) und werden immer wieder halbiert bzw. verdoppelt. Bei zahl1 werden zwar sehr kleine Zahlen erreicht (z.B. $5^{-324}$), allerdings niemals $0$ (daher die Endlosschleife).

Falsche Produkte

Die Variable zahl2 wird außerdem nur zu produkt hinzugefügt, wenn zahl1 % 2 == 1 ist. Bei ungerundeten Fließkommazahlen von zahl1, wie sie durch zahl1 = zahl1 / 2 zwangsläufig auftreten, besteht hierfür nur für $n>1$ überhaupt eine (seltene) Chance. Für $1>n>0$ kann dieser Fall überhaupt nicht mehr eintreten. Dies führt auch zu falschen Ergebnissen beim Ausgeben von produkt.

Ausgabe trotz infinite loop

Da in der Ausgabe nach $5^{-324}$ nicht $5^{-325}$ folgt, sondern die finale print-Aufforderung ausgeführt wird, scheint $5^{-325}$ mit $0$ gleichgesetzt zu werden. Wahrscheinlich tritt bei Gleitkommazahlen in Python hier der sogenannte Unterlauf oder underflow auf, bei dem 64bit nicht mehr ausreichen, um eine Zahl zu repräsentieren, was somit ungewollt die Zahl $0$ erzeugt.

Korrektur

Das Programm kann mit einer kleinen Änderung in Zeile 10 korrigiert werden (siehe unten). Zwingt man Python mit int(zahl1 / 2) zum Abrunden, so ergibt sich schnell zahl1 $=0$, was die ursprüngliche while-Schleife unterbricht und das korrekte Ergebnis ausgibt.

# Korrigierte Fassung
# Eingabe
zahl1 = int(input("Zahl 1: "))
zahl2 = int(input("Zahl 2: "))

# Verarbeitung
produkt = 0
while zahl1 > 0:
    if zahl1 % 2 == 1:
        produkt = produkt + zahl2
    zahl1 = int(zahl1 / 2) # <------ Änderung: int(...) rundet ab
    zahl2 = zahl2 * 2

# Ausgabe
print("Produkt: ", produkt)

(d) Zeichne ein Flussdiagramm zum Algorithmus.

flowchart TD
    id1([Start]) --> id2[/Eingabe z1/] --> id3[/Eingabe z2/] --> id4[produkt = 0]
    id4 --> id5{z1 > 0}
    id5 --> |yes| id6{z1 % 2 = 1}
    id5 --> |no| id7[/Ausgabe p/] --> id11([Stop])
    id6 --> |yes| id8[p = p + z2] 
    id6 --> |no| id9["z1 = int(z1 / 2)"]
    id8 --> id9["z1 = int(z1 / 2)"] --> id10["z2 = z2 * 2"] --> id5

    style id1 stroke: #ff8080, stroke-width: 4px
    style id11 stroke: #ff8080, stroke-width: 4px