Wir schreiben einen "Taschenrechner" in C #. Teil I. Wertberechnung, Ableitung, Vereinfachung und andere Gänse

Hallo!

Aus irgendeinem Grund ist unser Taschenrechner mit etwas verbunden, das jeder Anfänger schreiben sollte. Vielleicht, weil historisch gesehen Computer für diesen Zweck geschaffen wurden, um zu zählen. Aber wir werden einen schwierigen Taschenrechner schreiben, natürlich nicht sympisch, sondern um grundlegende algebraische Operationen wie Differenzierung, Vereinfachung und Funktionen wie Kompilieren ausführen zu können, um Berechnungen zu beschleunigen.


Wir nehmen die Kekse aus dem neuen Jahr und fahren los!

Ausdrucksassemblierung

Was ist ein Ausdruck?

Dies ist natürlich keine Zeile. Es ist ziemlich offensichtlich, dass eine mathematische Formel entweder ein Baum oder ein Stapel ist, und hier hören wir beim ersten Mal auf. Das heißt, jeder Knoten, jeder Knoten dieses Baums ist eine Art von Operation, Variable oder Konstante.



Eine Operation ist entweder eine Funktion oder ein Operator, im Prinzip ungefähr dasselbe. Ihre Kinder sind die Argumente einer Funktion (Operator).

Klassenhierarchie in Ihrem Code

Natürlich kann die Implementierung beliebig sein. Die Idee ist jedoch, dass, wenn Ihr Baum nur aus Knoten und Blättern besteht, diese unterschiedlich sind. Deshalb nenne ich diese "Dinge" - Entitäten. Daher wird die obere Klasse die abstrakte Klasse Entity sein.


Darüber hinaus wird es vier Nachfolgeklassen geben: NumberEntity, VariableEntity, OperatorEntity, FunctionEntity.

Wie erstelle ich einen Ausdruck?

Zunächst erstellen wir einen Ausdruck im Code, d.h.

var x = new VariableEntity("x"); var expr = x * x + 3 * x + 12; 

Wenn Sie eine leere Klasse "VariableEntity" deklarieren, wird ein solcher Code einen Fehler auslösen. Sie sagen, dass sie nicht wissen, wie sie multiplizieren und summieren sollen.

Operatoren überschreiben

Eine sehr wichtige und nützliche Funktion in den meisten Sprachen, mit der Sie die Ausführung von Rechenoperationen anpassen können. Es ist syntaktisch je nach Sprache unterschiedlich implementiert. Zum Beispiel eine Implementierung in C #

 public static YourClass operator +(YourClass a, YourClass b) { return new YourClass(a.ToString() + b.ToString()); } 

Weitere Informationen zum Überschreiben von Anweisungen in C #
Die Rübe wird hier umgesetzt.

(Nicht) explizites Casting

In kompilierten Sprachen wie C # ist so etwas normalerweise vorhanden und ermöglicht es Ihnen, den Typ bei Bedarf ohne einen zusätzlichen Aufruf von myvar.ToAnotherType () umzusetzen. So wäre es zum Beispiel bequem zu schreiben

 NumberEntity myvar = 3; 

Anstelle des Üblichen

 NumberEntity myvar = new NumberEntity(3); 

Mehr zum Typ Casting in C #
Die Rübe ist auf dieser Linie implementiert.

Hängen

Die Entity-Klasse verfügt über ein untergeordnetes Feld. Dies ist nur eine Liste von Entities, die die Argumente für diese Entity sind.


Wenn wir eine Funktion oder einen Operator aufrufen, sollten wir eine neue Entität erstellen und die untergeordneten Elemente einfügen, von denen aus die Funktion oder der Operator aufgerufen wird. Zum Beispiel sollte der theoretische Betrag ungefähr so ​​aussehen:

 public static Entity operator +(Entity a, Entity b){ var res = new OperatorEntity("+"); res.Children.Add(a); res.Children.Add(b); return res; } 

Das heißt, wenn wir nun Entität x und Entität 3 haben, gibt x + 3 die Essenz des Summenoperators mit zwei Kindern zurück: 3 und x. So können wir Ausdrucksbäume bauen.

Ein Funktionsaufruf ist einfacher und nicht so schön wie bei einem Operator:

 public Entity Sin(Entity a) { var res = new FunctionEntity("sin"); res.Children.Add(a); return res; } 

Das Aufhängen in Rüben ist hier implementiert.

Ok, wir haben einen Ausdrucksbaum erstellt.

Variablensubstitution

Hier ist alles sehr einfach. Wir haben eine Entität - wir prüfen, ob es sich um eine Variable handelt. Wenn ja, geben wir den Wert zurück, andernfalls durchlaufen wir die untergeordneten Elemente.

Diese riesige 48-zeilige Datei implementiert eine solch komplexe Funktion.

Wertberechnung

Eigentlich für was das alles ist. Hier sollen wir Entity eine Art Methode hinzufügen

 public Entity Eval() { if (IsLeaf) { return this; } else return MathFunctions.InvokeEval(Name, Children); } 

Das Blatt ist unverändert, aber für alles andere haben wir eine benutzerdefinierte Berechnung. Ich werde noch einmal nur ein Beispiel geben:

 public static Entity Eval(List<Entity> args) { MathFunctions.AssertArgs(args.Count, 1); var r = args[0].Eval(); if (r is NumberEntity) return new NumberEntity(Number.Sin((r as NumberEntity).Value)); else return r.Sin(); } 

Wenn das Argument eine Zahl ist, erzeugen wir eine numerische Funktion, andernfalls geben wir sie so zurück, wie sie war.

Nummer?

Dies ist die einfachste Einheit, Nummer. Daran können arithmetische Operationen durchgeführt werden. Standardmäßig ist es komplex. Er hat auch Operationen wie Sin, Cos und einige andere definiert.

Bei Interesse wird Nummer hier beschrieben.

Derivat

Jeder kann die Ableitung numerisch berechnen, und eine solche Funktion wird wirklich in einer Zeile geschrieben:

 public double Derivative(Func<double, double> f, double x) => (f(x + 1.0e-5) - f(x)) * 1.0e+5; 

Aber wir wollen natürlich ein analytisches Derivat. Da wir bereits einen Ausdrucksbaum haben, können wir jeden Knoten gemäß der Differenzierungsregel rekursiv ersetzen. Es sollte ungefähr so ​​funktionieren:



Hier zum Beispiel, wie der Betrag in meinem Code implementiert ist:

 public static Entity Derive(List<Entity> args, VariableEntity variable) { MathFunctions.AssertArgs(args.Count, 2); var a = args[0]; var b = args[1]; return a.Derive(variable) + b.Derive(variable); } 

Aber die Arbeit

 public static Entity Derive(List<Entity> args, VariableEntity variable) { MathFunctions.AssertArgs(args.Count, 2); var a = args[0]; var b = args[1]; return a.Derive(variable) * b + b.Derive(variable) * a; } 

Und hier ist eine Problemumgehung an sich:

 public Entity Derive(VariableEntity x) { if (IsLeaf) { if (this is VariableEntity && this.Name == x.Name) return new NumberEntity(1); else return new NumberEntity(0); } else return MathFunctions.InvokeDerive(Name, Children, x); } 

Dies ist die Entity-Methode. Und wie wir sehen, hat das Blatt nur zwei Zustände - entweder ist es eine Variable, nach der wir unterscheiden, dann ist ihre Ableitung 1 oder es ist eine Konstante (Zahl oder VariableEntity), dann ist ihre Ableitung 0 oder ein Knoten, dann gibt es eine Referenz nach Namen (InvokeDerive) bezieht sich auf das Funktionsverzeichnis, in dem sich das gewünschte befindet (z. B. die Summe oder der Sinus).

Beachten Sie, dass ich so etwas wie dy / dx hier nicht belasse und sofort sage, dass die Ableitung der Variablen , durch die wir nicht unterscheiden, 0 ist. Aber hier wird es anders gemacht.

Alle Unterscheidungen werden in einer Datei beschrieben , weitere sind jedoch nicht erforderlich.

Vereinfachung des Ausdrucks. Muster

Eine Vereinfachung des Ausdrucks ist grundsätzlich nicht trivial. Welcher Ausdruck ist zum Beispiel einfacher: $$$x ^ 2 - y ^ 2$oder $$$(x - y) (x + y)$? Wir halten uns jedoch an einige Ideen und möchten auf deren Grundlage Regeln aufstellen, die den Ausdruck genau vereinfachen.

Es ist möglich, bei jedem Eval zu schreiben, dass, wenn wir die Summe haben und die Kinder arbeiten, wir vier Optionen aussortieren und wenn irgendwo etwas gleich ist, wir den Faktor herausnehmen ... Aber das will ich natürlich nicht. Daher können Sie das System von Regeln und Mustern erraten. Also, was wollen wir? So etwas wie diese Syntax:

 { any1 / (any2 / any3) -> any1 * any3 / any2 }, { const1 * var1 + const2 * var1 -> (const1 + const2) * var1 }, { any1 + any1 * any2 -> any1 * (Num(1) + any2) }, 

Hier ist ein Beispiel für einen Baum, in dem ein Teilbaum gefunden wurde (grün eingekreist), der dem Muster any1 + const1 * any1 entspricht (any1 ist orange eingekreist).



Wie Sie sehen, ist es für uns manchmal wichtig, dass dieselbe Entität wiederholt wird, um beispielsweise den Ausdruck x + a * x zu verkürzen. Wir müssen x dabei haben, da x + a * y nicht mehr reduziert wird. Daher müssen wir einen Algorithmus erstellen, der nicht nur überprüft, ob der Baum mit dem Muster übereinstimmt, sondern auch

1. Stellen Sie sicher, dass dasselbe Objektmuster mit demselben Objekt übereinstimmt.
2. Aufschreiben, was was entspricht, dann ersetzen.

Der Einstiegspunkt sieht ungefähr so ​​aus:

 internal Dictionary<int, Entity> EqFits(Entity tree) { var res = new Dictionary<int, Entity>(); if (!tree.PatternMakeMatch(this, res)) return null; else return res; } 

In tree.PaternMakeMatch füllen wir das Wörterbuch rekursiv mit Schlüsseln und ihren Werten. Hier ist ein Beispiel für eine Liste von Musterentitäten selbst:

 static readonly Pattern any1 = new Pattern(100, PatType.COMMON); static readonly Pattern any2 = new Pattern(101, PatType.COMMON); static readonly Pattern const1 = new Pattern(200, PatType.NUMBER); static readonly Pattern const2 = new Pattern(201, PatType.NUMBER); static readonly Pattern func1 = new Pattern(400, PatType.FUNCTION); 

Wenn wir any1 * const1 - func1 usw. schreiben, hat jeder Knoten eine Nummer - das ist der Schlüssel. Mit anderen Worten, wenn Sie das Wörterbuch ausfüllen, erscheinen diese Zahlen als Schlüssel: 100, 101, 200, 201, 400 ... Und wenn Sie einen Baum bauen, werden Sie den Wert des Schlüssels betrachten und ihn ersetzen.

Hier umgesetzt .

Vereinfachung. Baumsortierung

In dem Artikel , den ich bereits angesprochen habe, hat der Autor beschlossen, es einfach zu machen und praktisch nach dem Hash des Baumes zu sortieren. Er schaffte es, a und -a, b + c + b auf 2b + c zu reduzieren. Aber wir wollen natürlich auch, dass (x + y) + x * y - 3 * x reduziert wird und im Allgemeinen kompliziertere Dinge.

Muster funktionieren nicht?

Im Allgemeinen sind Muster, was wir zuvor getan haben, eine unglaublich wunderbare Sache. Dadurch können Sie den Unterschied zwischen den Quadraten und der Summe der Quadrate von Sinus und Cosinus sowie anderen komplexen Dingen verringern. Die elementare Handfläche (((((x + 1) + 1) + 1) + 1) wird jedoch nicht reduziert, da die Hauptregel hier die Kommutativität der Terme ist. Daher besteht der erste Schritt darin, die "linearen Kinder" zu isolieren.

"Lineare Kinder"

Tatsächlich möchten wir für jeden Knoten der Summe oder Differenz (und übrigens des Produkts / der Division) eine Liste von Begriffen (Faktoren) erhalten.



Dies ist grundsätzlich unkompliziert. Lassen Sie die Funktion LinearChildren (Entity node) eine Liste zurückgeben, dann betrachten wir child in node.Children: Wenn child keine Summe ist, dann result.Add (child), andernfalls result.AddRange (LinearChildren (child)).

Nicht der schönste Weg hier umgesetzt.

Kinder gruppieren

Wir haben also eine Liste mit Kindern, aber wie geht es weiter? Angenommen, wir haben sin (x) + x + y + sin (x) + 2 * x. Selbstverständlich erhält unser Algorithmus fünf Terme. Als nächstes wollen wir nach Ähnlichkeit gruppieren, zum Beispiel sieht x wie 2 * x mehr aus als sin (x).

Hier ist eine gute Gruppierung:



Da die darin enthaltenen Muster die Umwandlung von 2 * x + x in 3 * x weiter verarbeiten.

Das heißt, wir gruppieren zuerst nach einem Hash und führen dann MultiHang durch - Konvertieren der n-ary-Summation in eine Binärzahl.

Knoten-Hash

Einerseits, $$$x$und $$$x + 1$sollte in einer Gruppe platziert werden. Auf der anderen Seite, falls verfügbar $$$a * x$in eine Gruppe setzen mit $$$y * (x + 1)$sinnlos.


Deshalb implementieren wir eine mehrstufige Sortierung. Erstens geben wir das vor $$$x + 1$- das Gleiche. Sortiert, beruhigt. Dann geben wir das vor $$$x + 1$kann nur mit anderen platziert werden $$$x + 1$. Und jetzt unsere $$$a * (x + 1)$und $$$y * (x + 1)$endlich zusammengetan. Ganz einfach umgesetzt:

 internal string Hash(SortLevel level) { if (this is FunctionEntity) return this.Name + "_" + string.Join("_", from child in Children select child.Hash(level)); else if (this is NumberEntity) return level == SortLevel.HIGH_LEVEL ? "" : this.Name + " "; else if (this is VariableEntity) return "v_" + Name; else return (level == SortLevel.LOW_LEVEL ? this.Name + "_" : "") + string.Join("_", from child in Children where child.Hash(level) != "" select child.Hash(level)); } 

Wie Sie sehen können, beeinflusst die Funktion die Sortierung in keiner Weise (natürlich, weil $$$f (x)$mit $$$x$im Allgemeinen nicht verbunden). Wie eine Variable, $$$x$mit $$$y$Nun, es klappt nicht, zu mischen. Die Konstanten und Operatoren werden jedoch nicht auf allen Ebenen berücksichtigt. In dieser Reihenfolge ist der Vereinfachungsprozess selbst

 public Entity Simplify(int level) { //      :   ,   ,     . . var stage1 = this.InnerSimplify(); Entity res = stage1; for (int i = 0; i < level; i++) { //     .    -  x  x+1 (  ),  -  x-1  x+1 (,   ),  -  x+1  x+1 ( ). switch (i) { case 0: res = res.Sort(SortLevel.HIGH_LEVEL); break; case 2: res = res.Sort(SortLevel.MIDDLE_LEVEL); break; case 4: res = res.Sort(SortLevel.LOW_LEVEL); break; } //    . res = TreeAnalyzer.Replace(Patterns.CommonRules, res).InnerSimplify(); } return res; } 

Ich sortiere den Baum hier .

"Zusammenstellung" von Funktionen

In Anführungszeichen - da es sich nicht um den IL-Code selbst handelt, sondern nur um einen sehr schnellen Befehlssatz. Aber es ist sehr einfach.

Ersatzproblem

Um den Wert einer Funktion zu berechnen, müssen wir zum Beispiel nur die Variablensubstitution und -eval aufrufen

 var x = MathS.Var("x"); var expr = x * x + 3; var result = expr.Substitute(x, 5).Eval(); 

Aber es funktioniert langsam, ungefähr 1,5 Mikrosekunden pro Sinus.

Anleitung

Um die Berechnung zu beschleunigen, führen wir eine Funktionsberechnung auf dem Stapel durch, und zwar:

1) Wir haben die FastExpression-Klasse entwickelt, die eine Liste von Anweisungen enthält

2) Beim Kompilieren werden die Anweisungen in umgekehrter Reihenfolge gestapelt, dh wenn es eine Funktion x * x + sin (x) + 3 gibt, sind die Anweisungen ungefähr so:

 PUSHVAR 0 //    0 - x CALL 6 //    6 -  PUSHCONST 3 CALL 0 //    0 -  PUSHVAR 0 PUSHVAR 0 CALL 2 CALL 0 

Als nächstes führen wir diese Anweisungen aus und geben die Nummer zurück.

Ein Beispiel für die Ausführung einer Summenanweisung:

 internal static void Sumf(Stack<Number> stack) { Number n1 = stack.Pop(); Number n2 = stack.Pop(); stack.Push(n1 + n2); } 

Der Sinus-Aufruf wurde von 1500ns auf 60ns reduziert (das System Complex.Sin arbeitet für 30ns).
Die Rübe wird hier umgesetzt.

Fuh, alles scheint vorerst zu sein. Es gibt zwar noch etwas zu erzählen, aber es scheint mir, dass der Umfang für einen Artikel ausreicht. Interessiert sich jemand für die Fortsetzung? Nämlich: Parsen aus einer Zeichenfolge, Formatieren in Latex, einem bestimmten Integral und anderen Extras.

Verknüpfen Sie das Repository mit dem gesamten Code sowie den Tests und Beispielen.


Vielen Dank für Ihre Aufmerksamkeit!