Nós escrevemos uma "calculadora" em C #. Parte I. Cálculo do valor, derivada, simplificação e outros gansos

Oi

Por alguma razão, nossa calculadora está associada a algo que todo iniciante deve escrever. Talvez porque historicamente os computadores para esse fim foram criados para contar. Mas escreveremos uma calculadora difícil, não simpatizante, é claro, mas poderemos executar operações algébricas básicas, como diferenciação, simplificação e recursos como compilação para acelerar os cálculos.


Pegamos os cookies restantes do ano novo e dirigimos!

Montagem de expressão

O que é uma expressão?

Claro, isso não é uma linha. É bastante óbvio que uma fórmula matemática é uma árvore ou uma pilha, e aqui paramos no início. Ou seja, cada nó, cada nó desta árvore, é algum tipo de operação, variável ou constante.



Uma operação é uma função ou um operador, em princípio, aproximadamente a mesma coisa. Seus filhos são os argumentos de uma função (operador).

Hierarquia de classes no seu código

Obviamente, a implementação pode ser qualquer. No entanto, a ideia é que, se a sua árvore consistir apenas em nós e folhas, eles serão diferentes. Portanto, eu chamo essas "coisas" - entidades. Portanto, a classe alta será a entidade abstrata da classe.


E também haverá quatro classes sucessoras: NumberEntity, VariableEntity, OperatorEntity, FunctionEntity.

Como construir uma expressão?

Primeiro, criaremos uma expressão no código, ou seja,

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

Se você declarar uma classe vazia VariableEntity, esse código gerará um erro, eles dizem que não sabem como multiplicar e somar.

Substituindo operadores

Um recurso muito importante e útil da maioria dos idiomas, permitindo personalizar a execução de operações aritméticas. É implementado sintaticamente de maneira diferente, dependendo do idioma. Por exemplo, uma implementação em C #

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

Saiba mais sobre como substituir instruções em C #
O nabo é implementado aqui .

Fundição (não) explícita

Em linguagens compiladas como C #, normalmente existe algo que permite converter o tipo, se necessário, sem uma chamada adicional para myvar.ToAnotherType (). Então, por exemplo, seria conveniente escrever

 NumberEntity myvar = 3; 

Em vez do habitual

 NumberEntity myvar = new NumberEntity(3); 

Mais sobre conversão de tipo em C #
O nabo é implementado nesta linha.

Pendurado

A classe Entity possui um campo Filhos - esta é apenas uma lista de Entity, que são os argumentos para essa entidade.


Quando chamamos uma função ou operador, devemos criar uma nova entidade e colocar nela os filhos dos quais a função ou operador é chamada. Por exemplo, a quantidade em teoria deve ser algo como isto:

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

Ou seja, agora se tivermos a entidade xe a entidade 3, x + 3 retornará a essência do operador de soma com dois filhos: 3 e x. Então, podemos construir árvores de expressão.

Uma chamada de função é mais simples e não é tão bonita quanto em um operador:

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

Pendurar nabos é implementado aqui .

Ok, criamos uma árvore de expressão.

Substituição variável

Tudo é extremamente simples aqui. Nós temos Entity - verificamos se é uma variável em si; nesse caso, retornamos o valor, caso contrário, percorremos os filhos.

Esse enorme arquivo de 48 linhas implementa uma função tão complexa.

Cálculo do valor

Na verdade, pelo que tudo isso é. Aqui devemos adicionar algum tipo de método ao Entity

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

A folha permanece inalterada, mas, para todo o resto, temos um cálculo personalizado. Mais uma vez, vou dar apenas um exemplo:

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

Se o argumento for um número, produziremos uma função numérica; caso contrário, retornaremos como era.

Número?

Esta é a unidade mais simples, número. Operações aritméticas podem ser executadas nele. Por padrão, é complexo. Ele também possui operações como Sin, Cos e outras definidas.

Se estiver interessado, o número é descrito aqui .

Derivada

Qualquer um pode calcular a derivada numericamente, e essa função é escrita verdadeiramente em uma linha:

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

Mas é claro que queremos uma derivada analítica. Como já temos uma árvore de expressão, podemos substituir recursivamente cada nó de acordo com a regra de diferenciação. Deve funcionar algo como isto:



Aqui, por exemplo, como a quantidade é implementada no meu código:

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

Mas o trabalho

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

E aqui está uma solução alternativa:

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

Este é o método da entidade. E, como vemos, a folha tem apenas dois estados - ou é uma variável pela qual nos diferenciamos, então sua derivada é 1 ou é uma constante (número ou VariableEntity), então sua derivada é 0 ou um nó, e existe uma referência por nome (InvokeDerive refere-se ao dicionário de funções, onde o desejado está localizado (por exemplo, a soma ou o seno)).

Note que eu não deixo algo como dy / dx aqui e digo imediatamente que a derivada da variável não pela qual nos diferenciamos é 0. Mas aqui é feita de maneira diferente.

Toda diferenciação é descrita em um arquivo , mas não é necessário mais.

Simplificação da expressão. Padrões

A simplificação da expressão geralmente não é trivial em princípio. Bem, por exemplo, qual expressão é mais simples: $$$x ^ 2 - y ^ 2$ou $$$(x - y) (x + y)$? Mas aderimos a algumas idéias e, com base nelas, queremos criar regras que simplifiquem com precisão a expressão.

É possível escrever em cada Eval que se tivermos a soma e as crianças forem obras, separaremos quatro opções e, se algo for igual em algum lugar, removeremos o fator ... Mas é claro que não quero fazer isso. Portanto, você pode adivinhar o sistema de regras e padrões. Então o que nós queremos? Algo como esta sintaxe:

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

Aqui está um exemplo de uma árvore na qual uma subárvore foi encontrada (circulada em verde) que corresponde ao padrão any1 + const1 * any1 (any1 encontrado é circulado em laranja).



Como você pode ver, às vezes é importante para nós que a mesma entidade seja repetida, por exemplo, para encurtar a expressão x + a * x, precisamos que x esteja lá e ali, porque x + a * y não é mais reduzido. Portanto, precisamos criar um algoritmo que não apenas verifique se a árvore corresponde ao padrão, mas também

1. Verifique se o mesmo padrão de entidade corresponde à mesma entidade.
2. Anotar o que corresponde ao que e depois substituir.

O ponto de entrada é mais ou menos assim:

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

E no tree.PaternMakeMatch, preenchemos recursivamente o dicionário com chaves e seus valores. Aqui está um exemplo de uma lista das próprias entidades padrão:

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

Quando escrevemos any1 * const1 - func1 e assim por diante, cada nó terá um número - esta é a chave. Em outras palavras, ao preencher o dicionário, esses números aparecerão como chaves: 100, 101, 200, 201, 400 ... E ao construir uma árvore, examinaremos o valor correspondente à chave e a substituiremos.

Implementado aqui .

Simplificação. Classificação de árvores

No artigo que eu já falei, o autor decidiu fazê-lo de maneira simples e ordenada praticamente pelo hash da árvore. Ele conseguiu reduzir ae -a, b + c + b para virar 2b + c. Mas, é claro, também queremos que (x + y) + x * y - 3 * x sejam reduzidos e, em geral, coisas mais complicadas.

Padrões não estão funcionando?

Em geral, o que fizemos antes, os padrões são uma coisa monstruosamente maravilhosa. Isso permitirá que você reduza a diferença entre os quadrados e a soma do quadrado do seno e do cosseno e outras coisas complexas. Mas a palma da mão elementar ((((((x + 1) + 1) + 1) + 1) + 1))) não será reduzida, porque a regra principal aqui é a comutatividade dos termos. Portanto, o primeiro passo é isolar os "filhos lineares".

"Filhos lineares"

Na verdade, para cada nó da soma ou diferença (e, a propósito, o produto / divisão), queremos obter uma lista de termos (fatores).



Isso é basicamente simples. Se a função LinearChildren (nó da entidade) retornar uma lista, veremos o filho no nó. Crianças: se o filho não for uma soma, result.Add (child), caso contrário result.AddRange (LinearChildren (child)).

Não é a maneira mais bonita implementada aqui .

Agrupando crianças

Então, temos uma lista de filhos, mas o que vem depois? Suponha que temos sin (x) + x + y + sin (x) + 2 * x. Obviamente, nosso algoritmo receberá cinco termos. Em seguida, queremos agrupar por similaridade, por exemplo, x parece 2 x mais que sin (x).

Aqui está um bom agrupamento:



Como os padrões nela continuarão a lidar com a conversão de 2 * x + x para 3 * x.

Ou seja, primeiro agrupamos um pouco de hash e depois fazemos o MultiHang - convertendo a soma n-ária em binária.

Hash do nó

Por um lado $$$x$e $$$x + 1$deve ser colocado em um grupo. Por outro lado, se disponível $$$a * x$colocar em um grupo com $$$y * (x + 1)$inútil.


Portanto, implementamos a classificação em vários níveis. Primeiro, fingimos que $$$x + 1$- a mesma coisa. Ordenado, acalmado. Então fingimos que $$$x + 1$só pode ser colocado com outras pessoas $$$x + 1$. E agora nossa $$$a * (x + 1)$e $$$y * (x + 1)$finalmente se uniram. Implementado de forma simples:

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

Como você pode ver, a função afeta a classificação de qualquer forma (é claro, porque $$$f (x)$com $$$x$geralmente não conectado no caso geral). Como uma variável, $$$x$com $$$y$Bem, não vai se misturar. Mas as constantes e operadores não são levados em consideração em todos os níveis. Nesta ordem, o próprio processo de simplificação

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

Eu ordeno a árvore aqui .

"Compilação" de funções

Entre aspas, pois não está no próprio código IL, mas apenas em um conjunto muito rápido de instruções. Mas é muito simples.

Problema substituto

Para calcular o valor de uma função, basta chamar a variável de substituição e eval, por exemplo

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

Mas funciona lentamente, cerca de 1,5 microssegundos por seno.

Instruções

Para acelerar o cálculo, fazemos um cálculo de função na pilha, a saber:

1) Criamos a classe FastExpression, que terá uma lista de instruções

2) Ao compilar, as instruções são empilhadas na ordem inversa, ou seja, se houver uma função x * x + sin (x) + 3, as instruções serão mais ou menos assim:

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

Em seguida, quando chamado, executamos essas instruções e retornamos Number.

Um exemplo de execução de uma declaração sum:

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

A chamada senoidal foi reduzida de 1500ns para 60ns (o sistema Complex.Sin funciona por 30ns).
O nabo é implementado aqui .

Fuh, tudo parece ser por enquanto. Embora ainda exista algo para contar, parece-me que o volume de um artigo é suficiente. Alguém está interessado na sequência? A saber: análise de uma string, formatação em látex, uma certa integral e outras guloseimas.

Link para o repositório com todo o código, bem como testes e amostras.


Obrigado pela atenção!