LEHRSTUHL A FÜR MATHEMATIK Prof. Dr. E. Görlich Wintersemester 99/00 7. 2. 2000 ______________________________________________________________________ 7) Programmieren in Maple ====================== Stichworte: diff, $, Programme schreiben, lokale Variablen, statements, rekursive Programme, option remember, runtime stack, remember table, Programm- ausfuehrung beobachten, pattern binding operator, save, read, mint. Zu Uebung 15, Aufgabe 5: ===================== Die Folge von reellen Polynomen p[n]; sei rekursiv definiert durch p[0](x) = 1;, und p[n+1](x) = 2*x^3*p[n](x)-x^2*diff(p[n](x),x); , n=0,1,2,... . Man zeige: Die Funktion f(x), die definiert ist durch f(x) = exp(-1/(x^2)); , falls 0 < x , f(x) = 0, , falls x = 0 , ist beliebig oft differenzierbar und erfuellt diff(f(x),`$`(x,n)) = p[n](1/x)*exp(-1/(x^2)); fuer alle 0 < x, n=1,2, ... . > restart: > f:=x->exp(-1/x^2); > diff(f(x),x); > x$2;x$3; > diff(f(x),x$2); > normal(%); > poly1:=proc() local result; result:=1; if args=0 then RETURN(result) fi end; > poly1(0); Das Programm beginnt mit "proc" und endet mit "end;". Es enthaelt eine einfache Schleife "if ... then ... fi". "RETURN(xyz)" bedeutet, dass das Programm, wenn es ueberhaupt bis zu dieser Stelle gelangt, abgebrochen wird mit der Ausgabe von "xyz". In unserem Fall wird "result" ausgegeben. Das ist eine Hilfsvariable, der wir vor Beginn der Schleife den Wert 1 gegeben haben. Der Befehl "local result" unmittelbar nach "proc()" bewirkt, dass die Hilfsvariable "result" eine lokale Variable wird, das heisst, dass ihr Wert nach Beendigung des Programms geloescht wird. Lokale Variablen haben die Eigenschaft, dass sie nicht mit globalen Variablen in Konflikt kommen koennen. Man darf zum Beispiel global "k:=1" festlegen und in einem Programm trotzdem "k" als Laufindex verwenden. ====================================================== Informationen ueber weitere Befehle, die in Programmen erlaubt sind, findet man unter > ?statement ====================================================== Mit "args" ist Vorsicht geboten! Das Programm "poly1" funktioniert nur, solange nur ein einziges Argument vorhanden ist und mit diesem keine Rechenoperation ausgefuehrt wird. Schon das Ausfuehren von args+1 fuehrt zu einer Fehlermeldung: > poly2:=proc() local result; result:=1; if args+1=1 then RETURN(result) fi end; > poly2(0); Statt "args" verwende "args[1]" auch dann, wenn nur ein einziges Argument vorhanden ist! Das folgende Programm fuehrt, wenn das Argument "n" ist, n-mal iterativ die obige Iterationsformel aus. Dazu dient die Schleife "for ... from ... to ... do ... od" Man beachte, dass die Iterationsformel in unserem Programm auf beiden Seiten die Groesse "result" enthalten darf: result:=2*x^3*result-x^2*diff(result,x); Hier wird zuerst die rechte Seite mit dem momentan vorhandenen Wert von "result" berechnet (also mit result=p[n](x); ) und dann das Ergebnis als neuer Wert von "result" gespeichert. Man braucht sich nicht darum zu kuemmern, dass bei jedem Schritt der Wert von k um eins erhoeht werden muss. Zur Kontrolle lassen wir in der folgenden vorlaeufigen Version des Programms sowohl das letzte Ergebnis als auch das letzte k anzeigen in Form einer Liste [result,k]: > poly3:=proc() local k, result; result:=1; if args[1]=0 then RETURN(result) else for k from 1 to args[1] do result:=2*x^3*result-x^2*diff(result,x); od fi; [result,k]; end; > poly3(1);poly3(2);poly3(3);poly3(4); Besser waere es, das Ergebnis mit "expand" auszumultiplizieren. Ausserdem entfernen wir jetzt die Anzeige von k. > poly4:=proc() local k, result; result:=1; if args[1]=0 then RETURN(result) else for k from 1 to args[1] do result:=expand(2*x^3*result-x^2*diff(result,x)); od fi; result; end; > poly4(0);poly4(1);poly4(2);poly4(3);poly4(4); Wir werden dieses Programm unten weiter diskutieren. Zunaechst zur Aufgabe 5: Wir koennen nun die Formel > diff(f(x),`$`(x,n)) = p[n](1/x)*exp(-1/(x^2)); verifizieren. Der folgende Ausdruck soll also gleich NULL sein fuer beliebiges natuerliches n: > test:=n->diff(exp(-1/x^2),x$n)-subs(x=1/x,poly4(n))*exp(-1/x^2); Dies kann nur ausgefuehrt werden, wenn n einen Zahlenwert hat: > test(1); > test(2); > normal(%); > normal(test(10)); > normal(test(100)); Dies ist natuerlich nur eine Verifikation, kein Beweis. ===================================================== Zum Beweis waere zu zeigen, dass beim Uebergang von der n-ten Ableitung > diff(f(x),`$`(x,n)) = p[n](1/x)*exp(-1/(x^2)); zur (n+1)-ten der Faktor p[n](1/x); in das durch die Rekursionsformel gegebene p[n+1](1/x); uebergeht: > diff(p[n](1/x)*exp(-1/x^2),x); > factor(%); Wir definieren p[n+1]; so, dass p[n+1](1/x); der entstandene Faktor ist: > p[n+1]:=x->-(D(p[n])(x)/x-2*p[n](x))*x^3; > expand(p[n+1](x)); Dies stimmt mit der Rekursionsformel ueberein. ====================================================== Eine "rekursive" Version des obigen Programms ===================================== Zeitnahme: > settime:=time():poly4(100):cpu_time=(time()-settime)*seconds; > settime:=time():poly4(120):cpu_time=(time()-settime)*seconds; > settime:=time():poly4(140):cpu_time=(time()-settime)*seconds; > length(poly4(140)); ======================================================== Rekursives Programm: > polyREC:=proc(n) option remember; if n=0 then 1 else expand(2*x^3*polyREC(n-1)-x^2*diff(polyREC(n-1),x) ) fi end; > polyREC(1); > polyREC(4); > polyREC(5); > polyREC(6); > polyREC(7); > polyREC(8); > settime:=time():polyREC(100): cpu_time=(time()-settime)*seconds; > settime:=time():polyREC(120): cpu_time=(time()-settime)*seconds; > settime:=time():polyREC(140): cpu_time=(time()-settime)*seconds; > length(polyREC(140)); Erklaerung: Zunaechst loeschen wir alle Speicher und laden das Programm ployREC neu. > restart; > polyREC:=proc(n) option remember; if n=0 then 1 else expand(2*x^3*polyREC(n-1)-x^2*diff(polyREC(n-1),x) ) fi end; Um zu beobachten, wie das rekursive Programm arbeitet, setzen wir die interface-Variable "verboseproc" von ihrem Normalwert 1 auf 2 herauf und die Variable "printlevel" von ihrem Normalwert 1 auf 100: > ?verboseproc > ?printlevel > printlevel; > interface(verboseproc=2); > printlevel:=(100); > polyREC(4); Erklaerung: ========= Wird das Programm mit Argument 4 aufgerufen: polyREC(4); dann passiert zunaechst nur folgendes: Dieser Aufruf wird in den "runtime stack" geschrieben, und es wird zweimal polyREC(3); aufgerufen. Auch das kann nur zu einem Befehlsaufruf ohne Ergebnis fuehren, also erscheinen polyREC(2); polyREC(1); im "runtime stack". Danach wird polyREC(0); aufgerufen, und das fuehrt zur Loesung "1". Nun arbeitet Maple den "runtime stack" rueckwaerts wieder auf: polyREC(1); kann jetzt geloest werden, anschliessend polyREC(2); . . . polyREC(4); . Warum ist diese Art der Progammierung schneller? Durch die "option remember" werden alle Ergebnisse, die dieses Programm im Laufe der aktuellen Maple-Sitzung erzielt hat, in eine sog. "remember table" geschrieben. Wenn man also polyREC(120); ausgefuehrt hat und danach polyREC(140); wissen will, braucht Maple nur noch die letzten 20 Iterationen auszufuehren. Den Inhalt der "remember table" kann man ansehen. Aber Vorsicht: Zuerst sollte man ueberlegen, wieviel Stoff darin zur Zeit abgelegt ist! Im vorliegenden Fall (nach dem Neustart) sind es nur fuenf harmlose Polynome. Setze "verboseproc" und "printlevel" zurueck: > interface(verboseproc=1):printlevel:=(1): > > ?remember > op(4,eval(polyREC)); Man kann diese Tabelle loeschen: > readlib(forget): forget(polyREC); > op(4,eval(polyREC)); Bemerkungen: ============ Der "runtime stack" ist begrenzt auf weniger als 3000 Zeilen: > length(polyREC(3000)): Maple laesst sich beim Abarbeiten eines grossen "runtime stack" im allgemeinen nicht durch Druecken des "STOP"-Knopfes stoeren. Die Begrenzung des "runtime stack" laesst sich umgehen, indem man die "remember table" in kleinen Schritten sukzessive erweitert. Das ist allerdings nur dann sinnvoll, wenn die Ergebnisse nur wenig Speicherplatz beanspruchen (also im vorliegenden Fall sicher nicht)! Dazu beobachte man das Anwachsen der Speicherbelegung bei den ersten Schritten (siehe "Bytes"-Angabe unten rechts am Rand des Maple-Fensters). Das Benutzen des "swap space" auf der Festplatte ist in den wenigsten Faellen sinnvoll. ======================================================== Zwei weitere Moeglichkeiten zur Fehlersuche in selbst geschriebenen Programmen: "trace" und "mint". 1) "trace" > restart: > polyREC:=proc(n) option remember; if n=0 then 1 else expand(2*x^3*polyREC(n-1)-x^2*diff(polyREC(n-1),x) ) fi end; > trace(polyREC); > polyREC(4); Bei einem erneuten Aufruf von polyREC(4) sieht man, dass nicht neu gerechnet sondern in der remember table nachgesehen wird: > polyREC(4); VORSICHT! Der folgende Befehl erzeugt eine unendliche Schleife. Sie laesst sich jedoch i.a. mittels des STOP-Knopfes beenden. Wenn Sie das am eigenen Rechner ausprobieren, sehen Sie auch, warum es so lange dauert, bis eine Reaktion erscheint: Der STOP-Befehl beendet die Kette von rekursiven Programm-Aufrufen im runtime-stack. An der Stelle entsteht eine Fehlermeldung: <-- ERROR in polyREC (now in polyREC) = interrupted} Diese wird nun von unten nach oben durch alle Programm-Aufrufe zurueckgereicht! > #polyREC(3/2); Der "trace"-Mechanismus muss nun wieder abgeschaltet werden: > untrace(polyREC); Verbesserung des Programms polyREC ================================== Man kann leicht verhindern, dass das Programm mit unerwuenschtem Argument gestartet wird, indem man den sogenannten "pattern binding operator" einbaut. Er besteht aus zwei Doppelpunkten und nur bewirkt, dass nur solche Eingaben akzeptiert werden, die vom angegebenen Typ sind. Der Typ muss zur Liste der Maple-Typen gehoeren. > ?type > type(0,nonnegint); > type(1,nonnegint); > Man beachte, dass an drei Stellen der Name "polyREC" durch "polyREC2" ersetzt werden muss: > polyREC2:=proc(n::nonnegint) option remember; if n=0 then 1 else expand(2*x^3*polyREC2(n-1)-x^2*diff(polyREC2(n-1),x) ) fi end; > polyREC2(0);polyREC2(4);polyREC2(3/2);polyREC2(Pi); ======================================================= Maple bietet ein weiteres Werkzeug an, mit dem man Programme auf Fehler untersuchen kann: "mint". > ?mint Der "mint syntax checker" kann nur ausserhalb des Maple Programms benutzt werden. Er ist nur auf Datenfiles anwendbar, die ein maple-Programm in Form von ascii-text enthalten. Also muessen wir zuerst unsere Programme "poly4" und "polyREC2" in dieser Form abspeichern (am eigenen Rechner bitte hier den Pfad anpassen!): > save polyREC2, `/home/goerlich/MAPLEfANA00/polyREC2`; Das Programm "poly4" ist nicht mehr im Maple-Speicher, da wir inzwischen einen Neustart gemacht haben. > save poly4, `/home/goerlich/MAPLEfANA00/poly4`; Also kopiere es her und lese es neu ein: > poly4:=proc() local k, result; result:=1; if args[1]=0 then RETURN(result) else for k from 1 to args[1] do result:= expand(2*x^3*result-x^2*diff(result,x)); od fi; result; end; Nun kann es gespeichert werden: > save poly4, `/home/goerlich/MAPLEfANA00/poly4`; Test: Nach Neustart sind beide Programme unbekannt: > restart: > poly4(2); polyREC2(2); Lese die Programme aus den gerade erzeugten files und teste sie: > read(`/home/goerlich/MAPLEfANA00/poly4`); > read(`/home/goerlich/MAPLEfANA00/polyREC2`): > poly4(2); polyREC2(2); Nun starte von einer Shell aus das Mint-Programm: Befehl: /usr/local/maple/bin/mint -i 4 poly4 /usr/local/maple/bin/mint -i 4 polyREC2 (Pfad bitte anpassen!) (unter Windows: Start, Programme, MapleV Release5.1, Mint Readme lesen! Nochmals Start, Programme, MapleV Release5.1, Mint Es erscheint ein Shell-Fenster. Abwarten, bis ein Dialogfeld erscheint. Dort die Option und den Programmnamen mit vollstaendigem Pfad eintragen, z.B.: C:\poly4 ) Hier die Ergebnisse als Kopie von der shell: goerlich@anteia:/home/goerlich/MAPLEfANA00 > /usr/local/maple/bin/mint -i 4 poly4 |\^/| Maple V Release 5.1 Diagnostic Program ._|\| |/|_. Copyright (c) 1981-1998 by Waterloo Maple Inc. All rights \ MINT / reserved. Maple and Maple V are registered trademarks of <____ ____> Waterloo Maple Inc. | Procedure poly4() on lines 1 to 3 These names were used as global names but were not declared: x These local variables were assigned a value but otherwise not used: k Local variable usage: k was assigned a value result was used as a value, assigned a value, used as a call-by-value arg Global variables used in this procedure: x was used as a value, used as a call-by-value arg System names used in this procedure: RETURN was called as a fcn args was used as a list or table diff was called as a fcn expand was called as a fcn Maple uses these names: RETURN defined throughout Maple, for evalhf args defined throughout Maple diff defined throughout Maple, for the convert routines, for the diff routines expand defined throughout Maple These functions were called: RETURN, diff, expand Global variables used in this file: poly4 was assigned a procedure No functions were called. goerlich@anteia:/home/goerlich/MAPLEfANA00 > /usr/local/maple/bin/mint -i 4 polyREC2 |\^/| Maple V Release 5.1 Diagnostic Program ._|\| |/|_. Copyright (c) 1981-1998 by Waterloo Maple Inc. All rights \ MINT / reserved. Maple and Maple V are registered trademarks of <____ ____> Waterloo Maple Inc. | Procedure polyREC2( n::nonnegint ) on lines 1 to 2 These names were used as global names but were not declared: x Parameter usage: n::nonnegint was used as a value Global variables used in this procedure: polyREC2 was called as a fcn x was used as a value, used as a call-by-value arg System names used in this procedure: diff was called as a fcn expand was called as a fcn Maple uses these names: diff defined throughout Maple, for the convert routines, for the diff routines expand defined throughout Maple These functions were called: diff, expand, polyREC2 Global variables used in this file: polyREC2 was assigned a procedure, assigned a function value x was used as a value No functions were called.