THOUGHT

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

Ich weiß ja auch nicht, warum Lisp kein Industriestandard wurde; allerdings ist folgendes laecherlich:

In Scheme kann ich die “accumulate”-Funktion aus dem SICP ohne Probleme implementieren. In Python habe ich mit `eval’ gerungen und muss jedes Argument als String angeben. Sprachen, die kein `eval’ haben, werden wohl gar keine solche Funktion definieren koennen und somit kaum abstrakt arbeiten koennen. Schlimm.

Python: http://pastecode.com/?show=m3128cab7
Scheme: http://pastecode.com/?show=mc4e5c48

Und nun sag mal jemand, dass sich Lisp nicht lohne.

So long.

Waehrend ich mir nun nachts mein Textadventure programmiere, um es dann bis zu meinem Referat hoffentlich auch in OOP-Version als (falls die Zeit reicht) Vergleich von prozeduralem und objektorientiertem Programmieren zu bringen, (ja, dieser Satz hoert nicht allzu schnell auf) ist mir ein wahrhaft wunderbarer, geekiger und Python involvierender Witz eingefallen, obwohl die Bewegung des Spielers damit gar nichts zu tun hat: (Und ja, Mark Twain, du darfst in deinem Grabe fluchen, dass das Deutsche unendlich lange Saetze moeglich macht.)

So … wie waere es, wenn man sich selbst als self auf einem T-Shirt bezeichnet. Dann enthaelt die Liste foo = self.name.split(' ') , wenn man die einzelnen Buchstaben jeweils mit einem Leerzeichen trennt, als letzten Index (d.h. foo[-1]) ‘z’. Diesen vertauschen wir gekonnt mit einem x, indem wir foo[-1] = 'x' eingeben. Um das ‘i’ wegzubekommen nutzen wir foo.pop(-2) und haben auf den letzten 3 Indexen schon mal ‘S e x’. Da ‘M a r c o S e x’ nicht allzu viel Sinn macht, aendern wir das ab: ‘c’ und ‘o’ schmeißen wir mit foo.pop(4); foo.pop(3) raus. ‘r’ aendern wir in ‘g’ um, indem wir foo[2] = 'g' eingeben. Dann haetten wir ja schon ‘M a g S e x’. Da das der akribisch auf Details achtende Deutsche nicht stehen lassen kann, verbindet er das folgendermaßen: bar = "%s%s%s %s%s%s" % (foo[0], foo[1], foo[2], foo[3], foo[4], foo[5])
Ausgeben tun wir das per print bar.

Somit haetten wir einen netten String mit ‘Mag Sex’ und zugleich noch ein bisschen mit Python rumgespielt und somit ein bisschen mit Strings und Listen geuebt. Tolle Kombination aus Situationshumor und Lernen, oder?

Wenn ich das in Lisp hinbekomme, so lasse ich das auf ein T-Shirt drucken und werde ueber die verwirrten Gesichter lachen, denn es ist sehr unwahrscheinlich, dass ich auf der Stelle einem Lisphacker begegne. Und wenn doch, so wird er mich sicherlich ansprechen und sich als Geek outen. :)

So long, sagte der selbstsichere Pythonist, der mehr Kaffee benoetigt. (Ich haette den String auch mit ‘ner eigenen Funktion auftrennen koennten und haette somit keine umstaendliche Leerzeichensetzung, aber da haette ich nicht so viele Listenfunktionen abdecken koennen.)

(Optimierte Version, inklusive Probe, ob es ein vollkommenes Quadrat ist, sodass es einen Integer wiedergibt: http://paste.pocoo.org/show/60858/ ; da die Seite sich hier anscheinend an Aufrufen von ahnungslosen Schuelern erfreut, habe ich das mal geupdatet - so steht’s jedenfalls in meinen Funktionen. Fuer die Leute, die schon Python lernen, aber nicht wissen, dass “x^(1/2)” gleich die Quadratwurzel ist, sei dies hier nochmals erwaehnt.)

def sqroot(approx, num, steps):
    approx = float(approx)
    n = 0
    while n < steps:
        approx = (approx+(num/approx))/2
        n += 1
    if n == steps:
        return approx

(Geheiligt sei das pre-Tag, welches ich damals noch nicht kannte.)

Da das Berechnen von Quadratwurzeln mit dem Heron-Verfahren doch einige nuetzliche Dinge fuer den Programmieranfaenger beinhalten kann, werde ich hier mal sehr, sehr ausfuehrlich auf eine kleine Implementation in Python eingehen, damit sogar Personen, denen Python nichts sagt, in der Lage sein sollten, die Funktion zu verstehen.
(more…)