Estamos escrevendo uma "calculadora". Parte II Resolva equações, renderize em LaTeX, acelere funções para superlight

Oi

Então, na primeira parte, já fizemos um bom trabalho fazendo derivada, simplificação e compilação. Então, o que mais nossa calculadora simples pode fazer? Bem, pelo menos equações da forma

$$

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

definitivamente tem que decidir. Também é lindo desenhar esse caso em latech, e tudo ficará bem! Vamos lá!

Aceleração de compilação

Na última parte, compilamos a função para poder compilá-la uma vez e executá-la várias vezes no futuro.
Então, nós introduzimos a função

$$

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

No final da primeira parte, a velocidade dessa função era a seguinte:


Como podemos ver, há partes repetidas nessa função, por exemplo, $$$x ^ 2$ , e seria bom armazená-los em cache.

Para isso, apresentamos mais duas instruções PULLCACHE e TOCACHE. O primeiro empurrará o número no cache no endereço que passamos para ele na pilha. O segundo copiará ( stack.Peek() ) o último número da pilha para o cache, também em um endereço específico.

Resta criar uma tabela na qual, durante a compilação, escreveremos funções para armazenamento em cache. O que não vamos armazenar em cache? Bem, primeiro, o que acontece uma vez. As instruções extras para acessar o cache não são boas. Em segundo lugar, operações muito simples também não fazem sentido armazenar em cache. Bem, por exemplo, acessando uma variável ou número.

Ao interpretar a lista de instruções, teremos uma matriz pré-criada para armazenamento em cache. Agora, as instruções para esta função parecem

 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 

Depois disso, obtemos um resultado claramente melhor:

Nos nabos, tanto a compilação quanto a interpretação das instruções são implementadas aqui .

LaTeX

Este é um formato bem conhecido para gravar fórmulas matemáticas (embora não apenas elas!), Que é renderizado em belas imagens. Também está no hub, e todas as fórmulas que escrevo são apenas escritas neste formato.

Ter uma árvore de expressão torna a renderização em látex muito simples. Como fazer isso em termos de lógica? Então, nós temos o topo da árvore. Se é um número ou uma variável, tudo é simples. Se esse vértice, por exemplo, o operador de divisão, gostaríamos de mais $$$\ frac {a} {b}$ que $$$a / b$ , então, para a divisão, escrevemos algo como

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

Tudo é muito simples, como vemos. O único problema que encontrei durante a implementação é que não está claro como colocar os colchetes. Se nós apenas os empurrarmos para cada operador, teremos essas bobagens:

$$

$$\ esquerda (\ esquerda (\ esquerda (\ esquerda (x + 3 \ direita) + \ esquerda (a + b \ direita) \ direita) \ direita) + c \ direita)$$

No entanto, uma pessoa atenta notará imediatamente (e não como eu) que, se ela for completamente removida, ao construir uma expressão do formulário $$$c * (a + b)$ , vamos imprimir

$$

$$c * a + b$$

Resolvido de maneira simples, inserimos as prioridades dos operadores a la

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

E pronto, você é linda.

Latexirização feita aqui . E a palavra látex não existe, eu mesmo a inventei, não me chute por isso.

Solução de equação

Na verdade, do ponto de vista da matemática, você não pode escrever um algoritmo que encontre todas as soluções de alguma equação. Portanto, queremos encontrar o maior número possível de raízes, percebendo a inatingibilidade do objetivo final. Existem dois componentes: uma solução numérica (tudo é o mais simples possível) e analítica (mas isso é história).

Solução numérica. Método de Newton

Ele é extremamente simples, conhecendo a função $$$f (x)$ procuraremos a raiz usando uma fórmula iterativa

$$

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

Como todos resolvemos em um plano complexo, podemos basicamente escrever um ciclo bidimensional que buscará soluções e depois retornará soluções únicas. Além disso, agora podemos encontrar a derivada da função analiticamente e, em seguida, ambas as funções $$$f (x)$ e $$$f (x) '$ compilar.

Newton está sentado aqui .

Solução analítica

Os primeiros pensamentos são bastante óbvios. Então, a expressão, as raízes da equação $$$a (x) * b (x)$ totalidade igual de raízes $$$a (x)$ e $$$b (x)$ , da mesma forma para a divisão:

 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 o seno, isso parecerá um pouco diferente:

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

Afinal, queremos encontrar todas as raízes, e não apenas as que são 0.

Depois de termos assegurado que a expressão atual não é um produto, e não outros operadores e funções facilmente simplificados, precisamos tentar encontrar um modelo para resolver a equação.

A primeira idéia é usar os padrões que criamos para simplificar a expressão. E, de fato, precisaremos aproximadamente disso, mas primeiro precisamos fazer uma substituição de variável. E de fato, para a equação

$$

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

não há modelo, mas para o par

$$

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

mesmo que exista.

Portanto, criamos uma função do tipo GetMinimumSubtree, que retornaria a substituição de variável mais eficiente. O que é um substituto eficaz? Esta é uma substituição em que nós

1. Maximize o uso desta substituição
   
2. Maximize a profundidade da árvore (para que na equação $$$\ sin (\ sin (x)) ^ 2 + 3$ tivemos uma substituição $$$\ sin (\ sin (x))$ )
   
3. Garantimos que, com essa substituição, substituímos todas as referências a uma variável, por exemplo, se na equação $$$\ sin (x) ^ 2 + \ sin (x) + x$ faremos uma substituição $$$t = \ sin (x)$ então tudo ficará ruim. Portanto, nesta equação, o melhor substituto para $$$x$ é $$$x$ (ou seja, não há um bom substituto), mas, por exemplo, em $$$\ sin (x) ^ 2 + \ sin (x) + c$ podemos fazer uma substituição com segurança $$$t = \ sin (x)$ .
   

Depois de substituir a equação, parece muito mais simples.

Polinomial

Então, a primeira coisa que fazemos, expr.Expand() - abre todos os colchetes para nos livrarmos da sujeira do formulário $$$x (x + 2)$ transformando em $$$x ^ 2 + 2x$ . Agora, após a divulgação, temos algo como

$$

Não é canônico? Primeiro, coletamos informações sobre cada monômio, aplicando "filhos lineares" (no último artigo) e expandindo todos os termos.

O que temos sobre o monômio? Um monômio é um produto de fatores, um dos quais é uma variável ou um operador do grau de uma variável e um número inteiro. Portanto, introduziremos duas variáveis, uma com grau e a outra com coeficiente. Em seguida, basta analisar os fatores e, a cada vez, garantiremos que $$$x$ até certo ponto, ou sem um diploma. Se encontrarmos byaku - retornaremos com nulo.


Ok, nós compilamos um dicionário no qual a chave é um grau (inteiro) e o valor é um coeficiente monomial. É assim que parece no exemplo anterior:

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

Aqui, por exemplo, a implementação da solução da equação quadrá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 ponto ainda não foi concluído (por exemplo, você precisa fazê-lo corretamente para polinômios cúbicos), mas, em geral, acontece aqui .

Varredura Reversa

Então, aqui fizemos uma substituição de tipo $$$t = \ arcsin (x ^ 3 + a ^ 2)$ , e agora queremos obter x a partir daí. Aqui, temos apenas uma implantação passo a passo de funções e 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$$

O trecho de código é mais ou menos assim:

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

O código para essas funções está aqui .

Tudo, a solução final das equações (tchau!) É algo como isto

1. Se conhecermos a função ou o operador zero, envie Solve para lá (por exemplo, se $$$a * b = 0$ em seguida, execute Resolver (a) e Resolver (b))
2. Encontre um substituto
3. Resolva como um polinômio, se possível
4. Para todas as soluções, implante uma substituição para obter a solução final
5. Se, como polinômio, não for resolvido e tivermos apenas uma variável, a resolveremos pelo método de Newton

Então hoje nós somos:

• Acelere a função compilada devido ao cache
• Renderizado em LaTeX
• Resolvemos uma pequena parte dos casos de equações

Provavelmente não vou falar sobre o cálculo numérico de uma determinada integral, pois é muito simples . Não falei sobre análise, pois recebi críticas sobre isso em um artigo anterior. A ideia era escrever a sua. No entanto, é necessário falar sobre como analisamos uma expressão de uma string?
O projeto está aqui .





E aqui estão alguns exemplos do que fizemos hoje

 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 

Obrigado pela atenção!