Nous écrivons une «calculatrice». Partie II Résolvez des équations, effectuez un rendu dans LaTeX, accélérez les fonctions pour surligner

Salut

Donc, dans la première partie, nous avons déjà fait du bon travail en faisant du dérivé, de la simplification et de la compilation. Alors, que devrait faire notre calculatrice simple? Eh bien, au moins les équations de la forme

$$

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

doivent certainement décider. C'est aussi beau de dessiner ce boîtier en latech, et ça ira très bien! C'est parti!

Accélération de la compilation

Dans la dernière partie, nous avons compilé la fonction afin de pouvoir la compiler une fois, puis l'exécuter plusieurs fois à l'avenir.
Donc, nous introduisons la fonction

$$

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

A la fin de la première partie, la vitesse de cette fonction était la suivante:


Comme nous pouvons le voir, il y a des parties répétitives dans cette fonction, par exemple, $$$x ^ 2$ , et ce serait bien de les mettre en cache.

Pour ce faire, nous introduisons deux instructions supplémentaires PULLCACHE et TOCACHE. Le premier poussera le numéro dans le cache à l'adresse que nous lui transmettrons sur la pile. Le second copiera ( stack.Peek() ) le dernier numéro de la pile dans le cache, également à une adresse spécifique.

Il reste à faire un tableau dans lequel lors de la compilation nous écrirons des fonctions pour la mise en cache. Ce que nous ne mettrons pas en cache? Eh bien, tout d'abord, ce qui se passe une fois. L'instruction supplémentaire pour accéder au cache n'est pas bonne. Deuxièmement, les opérations trop simples n'ont également aucun sens à mettre en cache. Eh bien, par exemple, accéder à une variable ou à un nombre.

Lors de l'interprétation de la liste d'instructions, nous aurons un tableau pré-créé pour la mise en cache. Maintenant, les instructions pour cette fonction ressemblent à

 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 

Après cela, nous obtenons un résultat nettement meilleur:

Dans les navets, la compilation et l'interprétation des instructions sont implémentées ici .

LaTeX

Il s'agit d'un format bien connu pour enregistrer des formules mathématiques (mais pas seulement!), Qui est rendu en belles images. C'est aussi sur le hub, et toutes les formules que j'écris sont juste écrites dans ce format.

Le fait d'avoir un arbre d'expression rend le rendu en latex très simple. Comment faire cela en termes de logique? Donc, nous avons le sommet de l'arbre. S'il s'agit d'un nombre ou d'une variable, alors tout est simple. Si ce sommet, par exemple, l'opérateur de division, nous aimerions plus $$$\ frac {a} {b}$ que $$$a / b$ , donc pour la division, nous écrivons quelque chose comme

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

Tout est très simple, comme on le voit. Le seul problème que j'ai rencontré lors de la mise en œuvre est qu'il n'est pas clair comment placer les crochets. Si nous les plaçons sur chaque opérateur, nous obtiendrons de telles absurdités:

$$

$$\ gauche (\ gauche (\ gauche (\ gauche (x + 3 \ droite) + \ gauche (a + b \ droite) \ droite) \ droite) + c \ droite)$$

Cependant, une personne attentive remarquera immédiatement (et pas comme moi) que si elles sont complètement supprimées, alors lors de la construction d'une expression de la forme $$$c * (a + b)$ , nous imprimerons

$$

$$c * a + b$$

Il est résolu simplement, on entre les priorités des opérateurs à la

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

Et voila, tu es belle.

Latexirisation effectuée ici . Et le mot latexise n'existe pas, je l'ai inventé moi-même, ne me bottez pas dessus.

Solution d'équation

En fait, du point de vue des mathématiques, vous ne pouvez pas écrire un algorithme qui trouve toutes les solutions d'une équation. Par conséquent, nous voulons trouver autant de racines différentes que possible, réalisant l'inaccessibilité de l'objectif final. Il y a deux composantes: une solution numérique (tout est aussi simple que possible) et analytique (mais c'est de l'histoire).

Solution numérique. La méthode de Newton

Il est extrêmement simple, connaissant la fonction $$$f (x)$ nous rechercherons la racine en utilisant une formule itérative

$$

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

Puisque nous résolvons tous dans un plan complexe, nous pouvons essentiellement écrire un cycle bidimensionnel qui recherchera des solutions, puis en retournera des uniques. De plus, nous pouvons maintenant trouver la dérivée de la fonction analytiquement, puis les deux fonctions $$$f (x)$ et $$$f (x) '$ compiler.

Newton est assis ici .

Solution analytique

Les premières pensées sont assez évidentes. Ainsi, l'expression, les racines de l'équation $$$a (x) * b (x)$ totalité égale de racines $$$a (x)$ et $$$b (x)$ , de même pour la division:

 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; } } ... 

Pour le sinus, cela sera un peu différent:

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

Après tout, nous voulons trouver toutes les racines, et pas seulement celles qui sont à 0.

Après nous être assurés que l'expression actuelle n'est pas un produit et pas d'autres opérateurs et fonctions facilement simplifiés, nous devons essayer de trouver un modèle pour résoudre l'équation.

La première idée est d'utiliser les motifs que nous avons créés pour simplifier l'expression. Et en fait, nous aurons besoin d'environ cela, mais nous devons d'abord faire un remplacement variable. Et en effet, à l'équation

$$

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

il n'y a pas de modèle, mais pour la paire

$$

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

même s'il existe.

Par conséquent, nous faisons une fonction du type GetMinimumSubtree, qui retournerait le remplacement de variable le plus efficace. Qu'est-ce qu'un remplacement efficace? C'est un tel remplacement dans lequel nous

1. Maximisez l'utilisation de ce remplacement
   
2. Maximisez la profondeur de l'arbre (de sorte que dans l'équation $$$\ sin (\ sin (x)) ^ 2 + 3$ nous avons eu un remplaçant $$$\ sin (\ sin (x))$ )
   
3. Nous nous assurons qu'avec ce remplacement, nous avons remplacé toutes les références à une variable, par exemple, si dans l'équation $$$\ sin (x) ^ 2 + \ sin (x) + x$ nous ferons un remplacement $$$t = \ sin (x)$ alors tout deviendra mauvais. Par conséquent, dans cette équation, le meilleur remplacement pour $$$x$ c'est $$$x$ (c'est-à-dire qu'il n'y a pas de bon remplacement), mais par exemple dans $$$\ sin (x) ^ 2 + \ sin (x) + c$ nous pouvons faire un remplacement en toute sécurité $$$t = \ sin (x)$ .
   

Après avoir remplacé l'équation, c'est beaucoup plus simple.

Polynôme

Donc, la première chose que nous faisons, nous faisons expr.Expand() - ouvre tous les crochets afin de se débarrasser de la boue du formulaire $$$x (x + 2)$ devenir $$$x ^ 2 + 2x$ . Maintenant, après la divulgation, nous obtenons quelque chose comme

$$

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

Pas canonique? Ensuite, nous collectons d'abord des informations sur chaque monôme, en appliquant des «enfants linéaires» (dans le dernier article) et en développant tous les termes.

Qu'avons-nous du monôme? Un monôme est un produit de facteurs, dont l'un est une variable, ou un opérateur du degré d'une variable et d'un entier. Par conséquent, nous introduirons deux variables, l'une aura un degré et l'autre un coefficient. Ensuite, passez en revue les facteurs, et chaque fois que nous nous assurons que $$$x$ dans une certaine mesure, ou sans diplôme du tout. Si nous rencontrons byaku - nous revenons avec null.


D'accord, nous avons compilé un dictionnaire dans lequel la clé est un degré (entier) et la valeur est un coefficient monôme. Voici à quoi cela ressemble dans l'exemple précédent:

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

Ici, par exemple, la mise en œuvre de la solution de l'équation quadratique

 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; } 

Ce point n'est pas encore terminé (par exemple, vous devez le faire correctement pour les polynômes cubiques), mais en général cela se produit ici .

Balayage inversé

Donc, ici, nous avons fait un remplacement de type $$$t = \ arcsin (x ^ 3 + a ^ 2)$ , et maintenant nous voulons obtenir x de là. Ici, nous avons juste un déploiement étape par étape des fonctions et des opérateurs, tels que

$$

$$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$$

L'extrait de code ressemble à ceci:

 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); ... 

Le code de ces fonctions est ici .

Tout, la solution finale des équations (au revoir!) Ressemble à ceci

1. Si nous connaissons la fonction ou l'opérateur zéro, envoyez-y Résoudre (par exemple, si $$$a * b = 0$ puis exécutez Solve (a) et Solve (b))
2. Trouver un remplaçant
3. Résoudre comme un polynôme si possible
4. Pour toutes les solutions, déployez un remplaçant pour obtenir la solution finale
5. Si, en tant que polynôme, il n'est pas résolu et que nous n'avons qu'une seule variable, nous le résolvons par la méthode de Newton

Aujourd'hui, nous sommes donc:

• Accélérez la fonction compilée en raison du cache
• Rendu dans LaTeX
• Nous avons résolu une petite partie des cas d'équations

Je ne vais probablement pas parler du calcul numérique d'une certaine intégrale, car c'est très simple . Je n'ai pas parlé d'analyse, car j'ai reçu des critiques à ce sujet dans un article précédent. L'idée était d'écrire la vôtre. Néanmoins, est-il nécessaire de parler de la façon dont nous analysons une expression à partir d'une chaîne?
Le projet est ici .





Et voici quelques exemples de ce que nous avons fait aujourd'hui

 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 

Merci de votre attention!