Berechnen der nten Wurzel (Python, Scheme)
Tuesday, June 17th, 2008Einmal von Python, um meinen alten Beitrag fuer Quadratwurzeln zu uebertrumpfen, und zum anderem per Scheme, um einfach die unglaubliche Ausdrucksfaehigkeit der Sprachen der LISP-Familie zum Ausdruck kommt.
Man koennte, natuerlich auch die mathematische Grundlagen von Python/Scheme ausnutzen und n**1/root (bzw. (expt n 1/root)) rechnen lassen und somit sich gar nicht um die Implementierung eines Verfahrens zur Berechnung einer Wurzel kuemmern; allerdings kann man davon nichts lernen.
Python:
from decimal import Decimal
def callRecNthroot(num=1, approx=1, root=2, steps=5):
if approx == 1:
approx /= root
num, approx = Decimal(str(num)), Decimal(str(approx))
return recNthroot(num, approx, root, steps)
def recNthroot(num, approx, root, steps)
if steps > 0
return recNthroot(num, (1/root)*((root-1)*approx + (num/(approx**(root-1))), root, (steps-1))
return approx
Eigentlich ganz verstaendlich, bis auf ein paar Einfluesse von mir und meinem eher funktionalen Hintergrund, der auch Faulheit enthaelt.
foo /= n
bedeutet
foo = foo/n
. Meinen funktionalen (Wtf? `funktionen’? War ich da besoffen?) Hintergrund sieht man bei der tail-recursion: Ich packe alle Veraenderungen in den erneuten Funktionsaufruf, auch wenn das recht nervig ist, wenn man das aus dem Kopf heraus macht. Der neue Wert von approx stimmt; das ist das Newtonverfahren, wenn man nicht ableiten kann bzw. gerade keine Ableitfunktion (ist sehr kurz) schreiben moechte. Ich habe in Python einfach mal das `steps’-Argument benutzt, anstatt eine Praezision zu definieren; solange man eine nicht allzu ferne Naeherung angibt, so sind i.d.R. alle Stellen bis steps^2 korrekt.
Scheme:
(define (enough-prec? a b prec)
(< (abs (- a b)) prec))
(define (nthroot n root)
(lambda (x)
(cond
((enough-prec? n (expt x root) 0.0001) x)
(else ((nthroot n root) (* (/ 1 root) (+ (* (- root 1) x) (/ n (expt x (- root 1))))))))))
(Der letzte Teil ist so ziemlich das Gleiche.)
Man ruft die Funktion per ((nthroot n root) <approximation>) (Vergessen, dass HTML die Kleiner- und Groeßerzeichen frisst.) auf; fuer die Leute, die kein Scheme koennen. Die Annaeherung sollte moeglichst eine Dezimalzahl sein, da Scheme ansonsten ganz stolz eine rationale Zahl hervorbringt, die u.U. lang und unverstaendlich ist. (Probiert etwa mal ((nthroot 1000 3) 15); zwar bekommt man schnell etwas zurueck, allerdings hat das bei mir in Guile fast 2 Zeilen verschlungen.) Nun aber zum Code: Die Funktion (enough-prec?) nimmt 3 Argumente; zwei Zahlen, die sie voneinander subtrahieren soll und danach den Betrag davon berechnen soll, und eine Praezision; recht trivial, noch. Jetzt kommen wir zur Hauptfunktion: Ich benutze (lambda), um eine anonyme Funktion zu benutzen, die recht nett und praktisch sind. In ihr benutze ich (cond), um zwei Faelle zu unterscheiden: Zum einem, ob genuegend Praezision erlangt wurde; falls dies der Fall sein sollte, so spuckt er meine Annaeherung aus. Wenn nicht, wird er (nthroot) mit selbem n und root, aber einem neuen Argument fuer (lambda), aufrufen; eine tail-recursion; oder eher mies uebersetzt: Endrekursion. Der Trick dabei: Durch (enough-prec?) wird er solange weiterrechnen, bis man die gewollte Praezision hat; hier ist es 0.0001.
Was wohl eher auf einem Taschenrechner landet? Letztere Methode, mit so viel Genauigkeit, wie der Rechner Stellen anzeigt. Durch einen Tastendruck wird wohl eine Abstraktionsfunktion, sagen wir mal (nroot) aufgerufen, die n und root benoetigt und daraus eine sinnvolle Approximation macht. Wenn der Wert zu hoch ist, etwa ((nthroot 8 3) 64), so koennte er ewig weiterrrechnen. (Die Naeherungsmethode wuerde so eine immer groeßer werdende Naeherung herausgeben.)
(so long and (more (fun understanding)))
