Estamos escribiendo una "calculadora". Parte II Resuelve ecuaciones, renderiza en LaTeX, acelera funciones para superluz

Hola

Entonces, en la primera parte, ya hicimos un buen trabajo haciendo derivación, simplificación y compilación. Entonces, ¿qué otra cosa debería hacer nuestra calculadora simple? Bueno, al menos ecuaciones de la forma

$$

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

Definitivamente tengo que decidir. También es hermoso dibujar este caso en latech, ¡y estará bien! Vamos!

Aceleración de compilación

En la última parte, compilamos la función para poder compilarla una vez y luego ejecutarla muchas veces en el futuro.
Entonces, presentamos la función

$$

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

Al final de la primera parte, la velocidad de esta función era la siguiente:


Como podemos ver, hay partes repetidas en esta función, por ejemplo, $$$x ^ 2$ , y sería bueno almacenarlos en caché.

Para hacer esto, presentamos dos instrucciones más PULLCACHE y TOCACHE. El primero empujará el número en el caché en la dirección que le pasamos a la pila. El segundo copiará ( stack.Peek() ) el último número de la pila a la caché, también en una dirección específica.

Queda por hacer una tabla en la que durante la compilación escribiremos funciones para el almacenamiento en caché. ¿Qué no vamos a almacenar? Bueno, en primer lugar, lo que pasa una vez. La instrucción adicional para acceder al caché no es buena. En segundo lugar, las operaciones que son demasiado simples tampoco tienen sentido almacenar en caché. Bueno, por ejemplo, acceder a una variable o número.

Al interpretar la lista de instrucciones, tendremos una matriz pre-creada para el almacenamiento en caché. Ahora las instrucciones para esta función se ven como

 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 

Después de eso obtenemos un resultado claramente mejor:

En los nabos, aquí se implementan tanto la compilación como la interpretación de las instrucciones.

LaTeX

Este es un formato bien conocido para grabar fórmulas matemáticas (¡aunque no solo ellas!), Que se representa en bellas imágenes. También está en el centro, y todas las fórmulas que escribo están escritas en este formato.

Tener un árbol de expresión hace que la representación en látex sea muy simple. ¿Cómo hacer esto en términos de lógica? Entonces, tenemos la copa del árbol. Si es un número o una variable, entonces todo es simple. Si este vértice, por ejemplo, el operador de división, nos gustaría más $$$\ frac {a} {b}$ que $$$a / b$ , entonces para la división escribimos algo como

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

Todo es muy simple, como vemos. El único problema que encontré durante la implementación es que no está claro cómo colocar los corchetes. Si los empujamos a cada operador, obtendremos tales tonterías:

$$

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

Sin embargo, una persona atenta notará de inmediato (y no como yo) que si se eliminan por completo, al construir una expresión del formulario $$$c * (a + b)$ , imprimiremos

$$

$$c * a + b$$

Se resuelve simplemente, ingresamos las prioridades de los operadores a la

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

Y voila, eres hermosa.

Latexirización hecha aquí . Y la palabra latexise no existe, la inventé yo mismo, no me patees por eso.

Solución de ecuaciones

En realidad, desde el punto de vista de las matemáticas, no puedes escribir un algoritmo que encuentre todas las soluciones de alguna ecuación. Por lo tanto, queremos encontrar tantas raíces diferentes como sea posible, dándonos cuenta de la imposibilidad de alcanzar el objetivo final. Hay dos componentes: una solución numérica (todo es lo más simple posible) y analítica (pero esto es historia).

Solución numérica. Método de Newton

Es extremadamente simple, conoce la función. $$$f (x)$ buscaremos la raíz usando una fórmula iterativa

$$

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

Como todos resolvemos en un plano complejo, básicamente podemos escribir un ciclo bidimensional que buscará soluciones y luego devolverá soluciones únicas. Además, ahora podemos encontrar la derivada de la función analíticamente, y luego ambas funciones $$$f (x)$ y $$$f (x) '$ compilar

Newton está sentado aquí .

Solución analítica

Los primeros pensamientos son bastante obvios. Entonces, la expresión, las raíces de la ecuación $$$a (x) * b (x)$ igual totalidad de raíces $$$a (x)$ y $$$b (x)$ , de manera similar para la división:

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

Para seno, esto se verá un poco diferente:

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

Después de todo, queremos encontrar todas las raíces, y no solo aquellas que son 0.

Después de asegurarnos de que la expresión actual no sea un producto, y no otros operadores y funciones fácilmente simplificados, debemos tratar de encontrar una plantilla para resolver la ecuación.

La primera idea es usar los patrones que hicimos para simplificar la expresión. Y, de hecho, necesitaremos aproximadamente esto, pero primero tenemos que hacer un reemplazo variable. Y de hecho, a la ecuación

$$

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

no hay plantilla, pero para el par

$$

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

incluso tal como existe.

Por lo tanto, hacemos una función del tipo GetMinimumSubtree, que devolvería el reemplazo variable más eficiente. ¿Qué es un reemplazo efectivo? Este es un reemplazo en el que

1. Maximiza el uso de este reemplazo
   
2. Maximiza la profundidad del árbol (de modo que en la ecuación $$$\ sin (\ sin (x)) ^ 2 + 3$ tuvimos un reemplazo $$$\ sin (\ sin (x))$ )
   
3. Nos aseguramos de que con este reemplazo hemos reemplazado todas las referencias a una variable, por ejemplo, si está en la ecuación $$$\ sin (x) ^ 2 + \ sin (x) + x$ haremos un reemplazo $$$t = \ sin (x)$ entonces todo se volverá malo. Por lo tanto, en esta ecuación, el mejor reemplazo para $$$x$ es $$$x$ (es decir, no hay un buen reemplazo), pero por ejemplo en $$$\ sin (x) ^ 2 + \ sin (x) + c$ podemos hacer un reemplazo con seguridad $$$t = \ sin (x)$ .
   

Después de reemplazar la ecuación parece mucho más simple.

Polinomio

Entonces, lo primero que hacemos, hacemos expr.Expand() - abre todos los corchetes para deshacernos de la basura del formulario $$$x (x + 2)$ convirtiéndose en $$$x ^ 2 + 2x$ . Ahora, después de la divulgación, obtenemos algo como

$$

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

¿No es canónico? Luego, primero recopilamos información sobre cada monomio, aplicando “hijos lineales” (en el último artículo) y ampliando todos los términos.

¿Qué tenemos sobre el monomio? Un monomio es un producto de factores, uno de los cuales es una variable, o un operador del grado de una variable y un número entero. Por lo tanto, introduciremos dos variables, una tendrá un grado y la otra un coeficiente. A continuación, solo repase los factores, y cada vez nos aseguramos de que $$$x$ hasta cierto punto, o sin un título en absoluto. Si nos encontramos con byaku, volvemos con nulo.


Bien, hemos compilado un diccionario en el que la clave es un grado (entero) y el valor es un coeficiente monomial. Esto es lo que parece para el ejemplo anterior:

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

Aquí, por ejemplo, la implementación de la solución de la ecuación cuadrática

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

Este punto aún no se ha completado (por ejemplo, debe hacerlo correctamente para polinomios cúbicos), pero en general sucede aquí .

Barrido inverso

Entonces, aquí hemos hecho algún tipo de reemplazo $$$t = \ arcsin (x ^ 3 + a ^ 2)$ , y ahora queremos obtener x desde allí. Aquí solo tenemos una implementación paso a paso de funciones y operadores, como

$$

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

El fragmento de código se ve así:

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

El código para estas funciones está aquí .

Todo, la solución final de las ecuaciones (¡adiós!) Se parece a esto

1. Si conocemos la función u operador cero, envíe Resolver allí (por ejemplo, si $$$a * b = 0$ luego ejecute Solve (a) y Solve (b))
2. Encuentra un reemplazo
3. Resolver como un polinomio si es posible
4. Para todas las soluciones, implemente un reemplazo para obtener la solución final
5. Si, como polinomio, no se resuelve y solo tenemos una variable, la resolvemos por el método de Newton

Entonces, hoy estamos:

• Acelerar la función compilada debido a la memoria caché
• Rendido en LaTeX
• Resolvimos una pequeña parte de los casos de ecuaciones.

Probablemente no voy a hablar sobre el cálculo numérico de cierta integral, ya que es muy simple . No hablé de análisis, ya que recibí críticas al respecto en un artículo anterior. La idea era escribir la tuya. Sin embargo, ¿es necesario hablar sobre cómo analizamos una expresión de una cadena?
El proyecto ya está aquí .





Y aquí hay un par de ejemplos de lo que hicimos hoy.

 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 

Gracias por su atencion!