Der FormelSolver stellt sich vor

Der FormelSolver ist ein Object, dass 30% des Gesamtaufwandes von ToneCirc ausmacht. Dieses Object
kommt überall dort zum Einsatz, wo in Scripten Formeln symbolisch verarbeitet und ausgerechnet werden
müssen.

Der FormelSolver übernimmt folgende Aufgaben:

1. symbolisches Differenzieren
2. symbolisches Optimieren
3. Compilieren von Formeln in eine ausführbare Stack-Form
4. Compilieren dieses Stack's in reinen Maschinen-Code
5. Berechnung der nach 3. oder 4. vorliegenden Compilate

Symbolisches Differenzieren:

Für das symb. Differenzieren verwende ich einen rein Zeichenketten-orientierten rekursiven Algorithmus.
Eine Formel wird dabei von Innen nach Außen (Klammer-Ebenen und Operations-Priroritäten werden
berücksichtigt) aufgelöst und mittels Substituierung in sogenannte Elementar-Operationen zerlegt. Auf jede
Elementar-Operation wird dann die entsprechende Differentations-Regel angewendet. Das Ergebniss dient
dann wieder als Substitutor für eine höhere Ebene (usw.).
Wenn man sich an die Rechen- und Klammerregeln hält und nur die Funktionen verwendet, die in dieser
Tabelle als differenzierbar gekennzeichnet sind, wird der FormelSolver jede beliebige Formel differenzieren.
Dabei ist die Anzahl der Klammer-Ebenen unbegrenzt (bis der Stack überläuft).

Am Beispiel der Formel  y = a*(1 + sin(x)*exp(b*x))/2 sieht, nach x differenziert, die sogenannte
Diff-Substitutions-Table (DST) so aus:

Nr U V Regel
0 x 1  
1 b*x b  
2 exp(U1) V1*exp(U1) Ketten-Regel
3 sin(U0) V0*cos(U0) Ketten-Regel
4 U3*U2 V3*U2 + U3*V2 Produkt-Regel
5 1 + U4 V4  
6 U5/2 0.5*V5  
7 a*U6 a*V6  

U und V werden zusammen mit der Nr als Substitutoren verwendet. Dabei fungiert U als Original und V als
Differenziertes.
Nachdem der rekursive Algorithmus diese Tabelle erzeugt hat, wird die Ergebniss-Formel durch Zurück-
Substituieren von oben nach unten zusammen gebaut. Das Ergebnis sieht danach so aus:

y = a*(0.5*(sin(x)*b*exp(b*x) + 1*cos(x)*exp(b*x)))

Ich habe hier ein paar Klammern weggelassen, sonst sähe es noch schlimmer aus. Das Ergebniss ist richtig, hat
aber eine nicht gerade optimale Form. Aber dafür haben wir ja den Optimierungs-Algorithmus.

Symbolisches Optimieren:

Für das symb. Optimieren verwende ich einen rekursiven Baum-Algorithmus.
Eine Formel wird dabei in sogenannte Operations-Ketten zerlegt (Klammer-Ebenen und Operations-Priroritäten
werden berücksichtigt) und in einer Baum-Struktur abgebildet. Mit Hilfe dieses Ketten-Baumes kann nun
die Optimierung relativ einfach und intelligent vonstatten gehen. Nach der Baum-Optimierung wird der Baum
wieder in eine Formel-Zeichenkette zurück verwandelt.

Am Beispiel der Formel  y = a*(1 + sin(x)*exp(b*x))/2 sieht der Baum dann so aus:

Der Baum beginnt bei der sogenannten TOT (Top of Tree) und schlängelt sich von Klammer- bzw. Prioritätsebene
zur nächsten Unteren bis zur Niedrigsten durch. Die niedrigsten Ketten dürfen logischerweise keine Zeiger enthalten.
Dort endet der Baum.
Die rote Bezeichnung kennzeichnet die Art der Kette. Es gibt folgende Ketten-Typen:

Prod Produkt-Kette (* /)
Sum Summations-Kette (+ -)
Pow Potenz-Kette (^)
Fu Funktions-Kette (sin, cos, ....)
Rel Relations-Kette (für Relations-Funktion)
Komma Komma-Kette (,)

Jede Kette kann Zahlen, Symbole oder auch Zeiger (auf die nächste untere Kette) beinhalten. Die Funktions-Kette
besteht immer nur aus einem Element. Bei Funktionen mit mehreren Argumenten befindet sich dort ein Zeiger
auf eine Komma-Kette. Das negative Vorzeichen als auch das Gleichheitszeichen werden als spezielle Funktionen
gewehrtet (Neg, Equ).
Während der Optimierung werden die Ketten durch Anwendung der verschiedenen Kürzungs-Regeln gelöscht,
dupliziert, zusammengefasst, zusammengerechnet, vereinfacht usw. Das geschieht in mehreren Durchläufen, solange
bis sich keine Veränderung der Baum-Struktur mehr ergibt. Das Management des Baumes wird dabei von der
sogenannten MTT (Main Tree Table, enthält alle Ketten-Zeiger) aus durchgeführt.

Beim symb. Optimieren gibt es noch eine zweite Stufe, die aber in ToneCirc nicht verwendet wird (zu hoher Rechenzeit-
Bedarf). Hier sind in einer sogenannten Optimations-Matching-Table (OMT) spezielle Kürzungs-Regeln aufgeführt,
die in der Formel-Zeichenkette zur direkten Substitution des vereinfachten Konstruktes führen.
Beispiele für Kürzungs-Konstrukte sind:

sin(#)^2 + cos(#)^2 --> 1
exp(0) --> 1
exp(1) --> c_e
sin(-#) --> -sin(#)
log(#) + log($) --> log(#*$)

Da #, $ nicht nur einfache Symbole sein können, sondern auch Formeln, erweist sich das Finden des richtigen Matches
als außergewöhnlich rechenaufwendig. Klammern- und Prioritätsregeln müssen nämlich eingehalten werden. Die OMT
ist fest im FormelSolver-Code enthalten, und beinhaltet zur Zeit nur wenige Kürzungs-Konstrukte. Da die OMT nur
aus Zeichenketten beteht, könnte man Sie nach Außen führen (als Script) und leicht von jederman erweiterbar gestalten.
Diese 2. Stufe könnt Ihr im FormelSolver-Dialog testweise einschalten (dazu weiter unten).

Compilierung einer Formel in den OP-Stack:

Ähnlich wie beim symb. Differenzieren, wird die Formel mittels eines rekursiven Algorithmus in Elementar-Operationen
zerlegt. Diese Operationen werden aber zusammen mit den Operanten in einen sogenannten Operation-Stack (OS)
hintereinanderweg geschrieben. 
Am Beispiel der Formel  y = a*(1 + sin(x)*exp(b*x))/2 sieht der OS dann so aus:

Operant1 Operant2 Result Operation
b x Z0 *
x Null Z1 sin
Z0 Null Z2 exp
Z1 Z2 Z3 *
1 Z3 Z4 +
Z4 2 Z5 /
Z5 a Z6 *

Den Aufbau des OS bezeichnet man als umgekehrt polnische Notation. Die Operationen werden von der niederen zur
höheren Ebene hin in den Stack geschrieben. Z wird als Substitutor-Symbol verwendet (Zwischen-Variable). Operanten
und Result werden als Adressen auf Feld-Inhalte gespeichert. Diese Felder (es gibt verschiedene Typen) beinhalten
das Symbol und den momentanen Wert der Variable/Konstante/Zwischenvariable. Speziel bei der Relations-Funktion
werden bei Op1 und Op2 die Adressen auf einen Sub-OP-Stack (Unterstack) gespeichert. Sub-Stacks können wiederum
Sub-Stacks enthalten usw.
Nach der eigentlichen Compilierung findet auch hier noch eine Optimierung statt. Hauptsächlich werden Doppel-
Operationen erkannt und beseitigt. Käme z.Bsp. exp(b*x) noch ein zweites mal vor, dann würde der Stack-Optimierungs-
Algo die Operations-Abfolge für exp(b*x) einmal löschen und die Zeiger entsprechend verbiegen.

Compilierung des OP-Stack in Maschinen-Code:

Optional kann der FormelSolver, um Geschwindigkeit zu gewinnen, den Inhalt des OP-Stacks als Maschinen-Code in
einen programminternen Buffer schreiben (Just in Time). Dabei wird für jede Operation eine festgelegte Code-Sequenz
generiert, die Adressen der Operanten und Ergebnisse müssen nur richtig eingesetzt werden. Es liegt auf der Hand,
dass über 95% der Befehle FPU-Kommandos sind (FPU: Floating Point Unit des Prozessors). Schwierig wird es aber
wenn Relationsfunktionen Sub-Stacks erzeugt haben. Dann müssen nämlich noch bedingte Sprung-Anweisungen aufgelöst
und eingefügt werden.
Der Maschinen-Code-Block wird mit einem Return (ret) abgeschlossen und kann somit als Sub-Routine ausgeführt
werden (wie siehe weiter unten).

Berechnung des Ergebnisses aus dem OP-Stack:

Da Operanten und Ergebnisse als Adresse vorliegen, läßt sich der OP-Stack einfach hintereinanderweg mit hoher
Geschwindigkeit abarbeiten. Die Formeln werden ja nur einmal compiliert, aber danach abertausende-male mit
wechselnden Werten berechnet.

Berechnung des Ergebnisses aus dem Maschinen-Code:

Da der Code als Sub-Routine im internen Buffer vorliegt, kann Dieser mit einem Maschinen-Call ausgeführt werden.
Das geschieht mit folgenden Inline-Assembler-Befehlen:

BYTE *pbuf = assemblybuf;
_asm
{
             mov eax, pbuf
             call eax
}

Wenn mit dem new-Operator oder der alloc-Funktion Speicher angefordert wird, dann werden die Rechte dieses
Speicher-Blockes erstaunlicherweise auf Executable gesetzt (nur mit Windows-XP getestet). Das eröffnet natürlich
auch die Möglichkeit, Code in ein Programm einzuschleusen und auszuführen (wunderbar für Hacker). Ihr kennt
ja die Buffer-Overflow-Geschichten. Ich habe mich aber richtig gefreut, dass ein vom Programm erzeugter Code auch
einfach ausgeführt werden kann.
ToneCirc verwendet Maschinen-Code auch beim Lösen des GLS mit dem Gauss-Algorithmus. Hier generiert der
Graph-Manager den Maschinen-Code, der keinerlei Indexierungs-, Schleifen- und Sprunganweisungen mehr enthält.

Testen des FormelSolvers mit dem FormelSolver-Dialog:

Über Menü:Tools/Test FormelSolver wird dieser Dialog geöffnet:

Die gewünschte Formel gibt man in das Formel-Feld ein, dann drückt man am besten die Tasten DiffFormel
CompileFormel und CompileDiffFormel in dieser Reihenfolge. Bei DiffFormel wird im Protocol-Fenster
die DST und die nichtoptimierte Diffenzierte angezeigt. Bei CompileFormel und CompileDiffFormel werden
nach jedem Optimierungs-Durchlauf jeweils der Ketten-Baum (in Listen-Schreibweise) und der OP-Stack
ausgegeben.
Bei X-Var-Symbol legt man das Symbol fest, nachdem differenziert werden soll. Mit diesem Symbol wird auch
unten im Chart die X-Achse gebildet. Bei Param-Symbols können Parameter-Symbole unter Zuweisung eines
Wertes definiert werden.
Mittels ViewChart wird die Original-Formel, die symbolisch Differenzierte sowie die numerisch Differenzierte
ausgerechnet und angezeigt. Den X-Achsen-Bereich legt man voher mit X-Start und X-End fest. Vorsicht mit
Null-Stellen, diese werden als Peek auf 5G angezeigt.
Die numerische und die symbolische Kurve müssen genau übereinander liegen (nur grün darf zu sehen sein).
Ist dies nicht der Fall, dann wurde die Formel (Klammer-Fehler) oder die Parameter nicht richtig eingegeben, 
oder es liegt ein Programmierfehler bei der symbolischen Differenzierung vor. Man sollte also bevor man
scriptet, den Formalismus hier erst testen.
Bei Ext Optimate kann die 2. Stufe der Optimierung (OMT-Algo) ein/aus-geschaltet werden.

Zurück zur Hauptseite