Wir schreiben einen "Taschenrechner". Teil II Gleichungen lösen, in LaTeX rendern, Funktionen auf Superlight beschleunigen

Hallo!

Im ersten Teil haben wir also bereits gute Arbeit geleistet: Ableitung, Vereinfachung und Kompilierung. Was sollte unser einfacher Taschenrechner sonst noch können? Nun, zumindest Gleichungen der Form

$$

$$(x - b) (\ tan (\ sin (x)) ^ 2 - 3 \ tan (\ sin (x)) + c) = 0$$

muss auf jeden fall entscheiden. Es ist auch schön, diesen Fall in Latech zu zeichnen, und es wird in Ordnung sein! Lass uns gehen!

Übersetzungsbeschleunigung

Im letzten Teil haben wir die Funktion kompiliert, damit wir sie einmal kompilieren und in Zukunft mehrmals ausführen können.
Also führen wir die Funktion ein

$$

$$\ sin (x ^ 2) + \ cos (x ^ 2) + x ^ 2 + \ sin (x ^ 2)$$

Am Ende des ersten Teils war die Geschwindigkeit dieser Funktion wie folgt:


Wie wir sehen können, gibt es sich wiederholende Teile in dieser Funktion, zum Beispiel $$$x ^ 2$ und es wäre schön, sie zwischenzuspeichern.

Dazu führen wir zwei weitere Anweisungen ein: PULLCACHE und TOCACHE. Der erste schiebt die Nummer im Cache an die Adresse, an die wir sie übergeben haben, auf den Stapel. Die zweite kopiert ( stack.Peek() ) die letzte Nummer vom Stack in den Cache, ebenfalls an einer bestimmten Adresse.

Es bleibt eine Tabelle zu erstellen, in die wir während der Kompilierung Funktionen für das Caching schreiben. Was werden wir nicht zwischenspeichern? Na erstens, was passiert einmal. Die zusätzliche Anweisung zum Zugriff auf den Cache ist nicht gut. Zweitens macht es keinen Sinn, zu einfache Vorgänge zwischenzuspeichern. Zum Beispiel auf eine Variable oder Zahl zugreifen.

Bei der Interpretation der Anweisungsliste erhalten Sie ein vorgefertigtes Array für das Caching. Nun sehen die Anweisungen für diese Funktion so aus

 PUSHCONST (2, 0) PUSHVAR 0 CALL powf TOCACHE 0 #   ,         , -  . CALL sinf TOCACHE 1 #      PULLCACHE 0 # ,   .    PULLCACHE 0 CALL cosf PULLCACHE 1 CALL sumf CALL sumf CALL sumf 

Danach erhalten wir ein deutlich besseres Ergebnis:

In Rüben werden hier sowohl die Erstellung als auch die Interpretation von Anweisungen implementiert.

LaTeX

Dies ist ein bekanntes Format zum Aufzeichnen von mathematischen Formeln (obwohl nicht nur sie!), Die in schöne Bilder gerendert werden. Es ist auch auf dem Hub, und alle Formeln, die ich schreibe, sind nur in diesem Format geschrieben.

Ein Ausdrucksbaum macht das Rendern in Latex sehr einfach. Wie geht das logisch? Wir haben also die Spitze des Baumes. Wenn es eine Zahl oder eine Variable ist, ist alles einfach. Wenn dieser Eckpunkt beispielsweise der Divisionsoperator ist, möchten wir mehr $$$\ frac {a} {b}$ als $$$a / b$ , also für die Teilung schreiben wir so etwas wie

 public static class Div { internal static string Latex(List<Entity> args) => @"\frac{" + args[0].Latexise() + "}{" + args[1].Latexise() + "}"; } 

Alles ist sehr einfach, wie wir sehen. Das einzige Problem, auf das ich während der Implementierung gestoßen bin, ist, dass nicht klar ist, wie die Klammern platziert werden sollen. Wenn wir sie nur auf jeden Operator schieben, werden wir solchen Unsinn bekommen:

$$

$$\ left (\ left (\ left (\ left (x + 3 \ right) + \ left (a + b \ right) \ right) + c \ right)$$

Eine aufmerksame Person wird jedoch sofort (und nicht wie ich) bemerken, dass, wenn sie vollständig entfernt wird, dies beim Erstellen eines Ausdrucks der Form geschieht $$$c * (a + b)$ Wir werden drucken

$$

$$c * a + b$$

Es wird einfach gelöst, wir geben die Prioritäten der Betreiber a la

 args[0].Latexise(args[0].Priority < Const.PRIOR_MUL) + "*" + args[1].Latexise(args[1].Priority < Const.PRIOR_MUL); 

Und voila, du bist wunderschön.

Latexirisierung hier gemacht . Und das Wort Latex gibt es nicht, ich habe es selbst erfunden, tritt mich nicht dafür.

Gleichungslösung

Tatsächlich kann man aus mathematischer Sicht keinen Algorithmus schreiben, der alle Lösungen einer Gleichung findet. Deshalb wollen wir so viele verschiedene Wurzeln wie möglich finden und die Unerreichbarkeit des Endziels erkennen. Es gibt zwei Komponenten: eine numerische Lösung (alles ist so einfach wie möglich) und eine analytische (aber das ist Geschichte).

Numerische Lösung. Newtons Methode

Er ist extrem einfach und kennt die Funktion $$$f (x)$ Wir werden nach der Wurzel mit einer iterativen Formel suchen

$$

$$x_ {n + 1} = x_n - \ frac {f (x)} {f (x) '}$$

Da wir alle in einer komplexen Ebene lösen, können wir im Grunde genommen einen zweidimensionalen Zyklus schreiben, der nach Lösungen sucht und dann eindeutige zurückgibt. Außerdem können wir jetzt die Ableitung der Funktion analytisch finden und dann beide Funktionen $$$f (x)$ und $$$f (x) '$ kompilieren.

Newton sitzt hier .

Analytische Lösung

Erste Gedanken sind ziemlich offensichtlich. Also der Ausdruck, die Wurzeln der Gleichung $$$a (x) * b (x)$ gleiche Gesamtheit der Wurzeln $$$a (x)$ und $$$b (x)$ , ähnlich für die Teilung:

 internal static void Solve(Entity expr, VariableEntity x, EntitySet dst) { if (expr is OperatorEntity) { switch (expr.Name) { case "mul": Solve(expr.Children[0], x, dst); Solve(expr.Children[1], x, dst); return; case "div": Solve(expr.Children[0], x, dst); return; } } ... 

Bei Sinus sieht das etwas anders aus:

 case "sinf": Solve(expr.Children[0] + "n" * MathS.pi, x, dst); return; 

Schließlich wollen wir alle Wurzeln finden und nicht nur die, die 0 sind.

Nachdem wir sichergestellt haben, dass der aktuelle Ausdruck kein Produkt und keine anderen leicht zu vereinfachenden Operatoren und Funktionen ist, müssen wir versuchen, eine Vorlage zum Lösen der Gleichung zu finden.

Die erste Idee ist, die von uns erstellten Muster zu verwenden, um den Ausdruck zu vereinfachen. Und in der Tat werden wir ungefähr das brauchen, aber zuerst müssen wir einen variablen Ersatz machen. Und zwar zur Gleichung

$$

$$\ sin (x) ^ 2 + \ sin (x) - 0,4 = 0$$

Es gibt keine Vorlage, sondern das Paar

$$

$$\ begin {cases} t ^ 2 + t - 0.4 = 0 \\ t = \ sin (x) \ end {cases}$$

so wie es existiert.

Daher erstellen wir eine Funktion vom Typ GetMinimumSubtree, die die effizienteste Variablenersetzung zurückgibt. Was ist ein wirksamer Ersatz? Dies ist so ein Ersatz, in dem wir

1. Maximieren Sie die Verwendung dieses Ersatzes
   
2. Maximieren Sie die Tiefe des Baumes (so dass in der Gleichung $$$\ sin (\ sin (x)) ^ 2 + 3$ Wir hatten einen Ersatz $$$\ sin (\ sin (x))$ )
   
3. Wir stellen sicher, dass wir mit dieser Ersetzung alle Referenzen auf eine Variable ersetzt haben, z. B. wenn in der Gleichung $$$\ sin (x) ^ 2 + \ sin (x) + x$ Wir werden einen Ersatz machen $$$t = \ sin (x)$ dann wird alles schlecht. Daher ist in dieser Gleichung der beste Ersatz für $$$x$ Das $$$x$ (das heißt, es gibt keinen guten Ersatz), aber zum Beispiel in $$$\ sin (x) ^ 2 + \ sin (x) + c$ Wir können sicher einen Ersatz machen $$$t = \ sin (x)$ .
   

Nach dem Ersetzen sieht die Gleichung viel einfacher aus.

Polynom

Als erstes machen wir expr.Expand() - öffne alle Klammern, um den Dreck des Formulars loszuwerden $$$x (x + 2)$ sich verwandeln in $$$x ^ 2 + 2x$ . Jetzt, nach der Enthüllung, bekommen wir so etwas wie

$$

$$c + x ^ 3 + 3x ^ 2 - a * x ^ 3 + x$$

Nicht kanonisch? Dann sammeln wir zuerst Informationen zu jedem Monom, wenden lineare Kinder an (im letzten Artikel) und erweitern alle Begriffe.

Was haben wir über das Monom? Ein Monom ist ein Produkt von Faktoren, von denen einer eine Variable oder ein Operator des Grades einer Variablen und einer ganzen Zahl ist. Daher werden wir zwei Variablen einführen, von denen eine einen Grad und die andere einen Koeffizienten hat. Als nächstes gehen Sie einfach die Faktoren durch, und jedes Mal stellen wir sicher, dass entweder dort $$$x$ in gewissem Umfang oder ohne Abschluss. Wenn wir byaku treffen, kehren wir mit null zurück.


Okay, wir haben ein Wörterbuch zusammengestellt, in dem der Schlüssel ein Grad (Integer) und der Wert ein Monomialkoeffizient ist. So sieht es im vorherigen Beispiel aus:

 0 => c 1 => 1 2 => 3 3 => 1 - a 

Hier zum Beispiel die Implementierung der Lösung der quadratischen Gleichung

 if (powers[powers.Count - 1] == 2) { var a = GetMonomialByPower(2); var b = GetMonomialByPower(1); var c = GetMonomialByPower(0); var D = MathS.Sqr(b) - 4 * a * c; res.Add((-b - MathS.Sqrt(D)) / (2 * a)); res.Add((-b + MathS.Sqrt(D)) / (2 * a)); return res; } 

Dieser Punkt ist noch nicht abgeschlossen (zum Beispiel müssen Sie ihn für kubische Polynome korrekt ausführen), aber im Allgemeinen geschieht dies hier .

Rückwärts-Sweep

Also, hier haben wir einen Typersatz gemacht $$$t = \ arcsin (x ^ 3 + a ^ 2)$ , und jetzt wollen wir x von dort bekommen. Hier haben wir nur eine schrittweise Bereitstellung von Funktionen und Operatoren, wie z

$$

$$t = \ arcsin (x ^ 3 + a ^ 2)$$

$$

$$\ sin (t) = x ^ 3 + a ^ 2$$

$$

$$\ sin (t) - a ^ 2 = x ^ 3$$

$$

$$(\ sin (t) - a ^ 2) ^ {\ frac {1} {3}} = x$$

Das Code-Snippet sieht ungefähr so ​​aus:

 switch (func.Name) { case "sinf": // sin(x) = value => x = arcsin(value) return FindInvertExpression(a, MathS.Arcsin(value), x); case "cosf": // cos(x) = value => x = arccos(value) return FindInvertExpression(a, MathS.Arccos(value), x); case "tanf": // tan(x) = value => x = arctan(value) return FindInvertExpression(a, MathS.Arctan(value), x); ... 

Der Code für diese Funktionen ist hier .

Alles, die endgültige Lösung der Gleichungen (Tschüss!) Sieht ungefähr so ​​aus

1. Wenn wir die Nullfunktion oder den Operator kennen, senden Sie Solve dorthin (zum Beispiel if $$$a * b = 0$ dann führe Solve (a) und Solve (b) aus
2. Finden Sie einen Ersatz
3. Nach Möglichkeit als Polynom lösen
4. Stellen Sie für alle Lösungen einen Ersatz bereit, um die endgültige Lösung zu erhalten
5. Wenn es als Polynom nicht gelöst wird und wir nur eine Variable haben, lösen wir es mit der Newton-Methode

Heute sind wir also:

• Durch Cache kompilierte Funktion beschleunigen
• In LaTeX gerendert
• Wir haben einen kleinen Teil der Gleichungen gelöst

Ich werde wahrscheinlich nicht über die numerische Berechnung eines bestimmten Integrals sprechen, da es sehr einfach ist . Ich habe nicht über das Parsen gesprochen, da ich in einem früheren Artikel Kritik darüber erhalten habe. Die Idee war, selbst zu schreiben. Müssen wir dennoch darüber sprechen, wie wir einen Ausdruck aus einer Zeichenfolge analysieren?
Das Projekt ist da .





Und hier sind ein paar Beispiele von dem, was wir heute gemacht haben

 var x = MathS.Var("x"); var y = MathS.Var("y"); var expr = x.Pow(y) + MathS.Sqrt(x + y / 4) * (6 / x); Console.WriteLine(expr.Latexise()); >>> {x}^{y}+\sqrt{x+\frac{y}{4}}*\frac{6}{x} 

$$${x} ^ {y} + \ sqrt {x + \ frac {y} {4}} * \ frac {6} {x}$

 var x = MathS.Var("x"); var expr = MathS.Sin(x) + MathS.Sqrt(x) / (MathS.Sqrt(x) + MathS.Cos(x)) + MathS.Pow(x, 3); var func = expr.Compile(x); Console.WriteLine(func.Substitute(3)); >>> 29.4752368584034 

 Entity expr = "(sin(x)2 - sin(x) + a)(b - x)((-3) * x + 2 + 3 * x ^ 2 + (x + (-3)) * x ^ 3)"; foreach (var root in expr.Solve("x")) Console.WriteLine(root); >>> arcsin((1 - sqrt(1 + (-4) * a)) / 2) >>> arcsin((1 + sqrt(1 + (-4) * a)) / 2) >>> b >>> 1 >>> 2 >>> i >>> -i 

Vielen Dank für Ihre Aufmerksamkeit!