Beispiel - Heron-Verfahren

Babylonisches Wurzelziehen

Die Babylonier haben schon vor langer Zeit ein Verfahren entwickelt, mit dem man sehr gut Näherungswerte für die Quadratwurzel einer Zahl berechnen kann.

Als Beispiel betrachten wir die Zahl a = 3. Ziel ist es, die Wurzel aus 3 näherungsweise zu bestimmen.

Die Idee des Heron-Verfahrens besteht darin, ein Quadrat mit dem Flächeninhalt 3 näherungsweise zu konstruieren. Ausgangspunkt bildet ein Rechteck mit dem Flächeninhalt 3 bestehend aus den Seitenlängen 3 und 1. Schritt für Schritt werden die Seitenlängen jetzt so verändert, dass das Rechteck quadratischer wird, sein Flächeninhalt aber 3 bleibt. (vgl. Wikipedia - Heron-Verfahren).

Zur Durchführung des Verfahrens wurden die folgenden Programme entwickelt:

Programm 1:

def heron(x, y):
    x = (x + y) / 2
    y = a / x
    return (x, y)

# Zahl, deren Wurzel bestimmt werden soll
a = 3
# Genauigkeit
genauigkeit = 0.001
# Seitenlaengen des Ausgangsrechtecks
(laenge, breite) = (a, 1)
# Betrag der Differenz der Seitelaengen
differenz = a - 1
while differenz > genauigkeit:
    (laenge, breite) = heron(laenge, breite)
    if laenge > breite:
        differenz = laenge - breite
    else:
        differenz = breite - laenge
# Ausgabe der Naeherungswerte
print(laenge, breite)

Programm 2:

def heron(x, y):
    global differenz
    x = (x + y) / 2
    y = a / x
    if x > y:
        differenz = x - y
    else:
        differenz = y - x
    return (x, y)

# Zahl, deren Wurzel bestimmt werden soll
a = 3
# Genauigkeit
genauigkeit = 0.001
# Seitenlaengen des Ausgangsrechtecks
(laenge, breite) = (a, 1)
# Betrag der Differenz der Seitelaengen
differenz = a - 1
while differenz > genauigkeit:
    (laenge, breite) = heron(laenge, breite)
# Ausgabe der Naeherungswerte
print(laenge, breite)

Programm 3:

def heron(a, x, y):
    x = (x + y) / 2
    y = a / x
    if x > y:
        d = x - y
    else:
        d = y - x
    return (x, y, d)

# Zahl, deren Wurzel bestimmt werden soll
zahl = 3
# Genauigkeit
genauigkeit = 0.001
# Seitenlaengen des Ausgangsrechtecks
(laenge, breite) = (zahl, 1)
# Betrag der Differenz der Seitelaengen
differenz = zahl - 1
while differenz > genauigkeit:
    (laenge, breite, differenz) = heron(zahl, laenge, breite)
# Ausgabe der Naeherungswerte
print(laenge, breite)

Aufgabe 1

(a) Teste erst einmal die drei Programme. Variiere auch die verschiedenen Daten (z.B. a = 4; g = 0.00001).

(b) Mache dir klar, dass hier tatsächlich das Heron-Verfahren benutzt wird.

Aufgabe 2

(a) Die verschiedenen Programmversionen unterscheiden sich in einigen Details. Welche Unterschiede kannst du erkennen?

(b) Welche heron-Funktion aus den verschiedenen Programmversionen könnte man als Baustein verwenden, welche besser nicht?

Aufgabe 3

Im folgenden Programm werden dieselben Variablenbezeichner im Haupt- und Unterprogramm benutzt.

Programm 4:

def heron(a, x, y):
    x = (x + y) / 2
    y = a / x
    if x > y:
        d = x - y
    else:
        d = y - x
    return (x, y, d)

# Zahl, deren Wurzel bestimmt werden soll
a = 3
# Genauigkeit
g = 0.001
# Seitenlaengen des Ausgangsrechtecks
(x, y) = (a, 1)
# Betrag der Differenz der Seitelaengen
d = a - 1
while d > g:
    (x, y, d) = heron(a, x, y)
# Ausgabe der Naeherungswerte
print(x, y)

Teste, ob das gutgehen kann.