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