Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой | | ДОСТУПНЫЙ ОТДЫХ
Интересное

Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

Привет!

Итак, в первой части мы уже неплохо поработали, сделав производную, упрощение, и компиляцию. Так, а что еще должен уметь наш простенький калькулятор? Ну хотя бы уравнения вида

Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

точно должен решать. А еще красиво нарисовать это дело в латехе, и будет прямо хорошо! Погнали!

Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

ДисклеймерИ хотя код приведен здесь на C#, здесь его так мало, что незнание языка или ненависть к нему не должны сильно затруднить чтение.

Ускорение компиляции
В прошлой части мы сделали компиляцию функции, чтобы можно было один раз скомпилировать, и в дальнейшем много раз запускать.
Итак, введем функцию

Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

На окончание первой части скорость этой функции была такой:

Метод
Время (в наносекундах)

Substitute
6800

Наша скомпилированная функция
650

Эта жа функция, написанная прямо в коде
430

Что?Substitute — классический способ подсчета значения выражения, то есть например
var x = MathS.Var(«x»);
var expr = x + 3 * x;
Console.WriteLine(expr.Substitute(x, 5).Eval());
>>> 20

Наша скомпилированная функция — это когда мы делаем так же, но предварительно скомпилировав ее
var x = MathS.Var(«x»);
var expr = x + 3 * x;
var func = expr.Compile(x);
Console.WriteLine(func.Substitute(5));

Функция, написанная прям в коде, это когда мы делаем
static Complex MyFunc(Complex x)
=> x + 3 * x;

Как мы могли заметить, в этой функции есть повторяющиеся части, например, Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой, и неплохо было бы их закешировать.

Для этого введем еще две инструкции PULLCACHE и TOCACHE. Первая будет класть в стек число, лежащее в кеше по адресу, который мы ей передаем. Вторая будет копировать(stack.Peek()) последнее число из стека в кеш, тоже по определенному адресу.

Остается сделать таблицу, в которую при компиляции мы будем записывать функции для кеширования. Что мы не будем кешировать? Ну во-первых то, что встречается один раз. Лишняя инструкция обращения к кешу — нехорошо. Во-вторых, слишком простые операции тоже смысла кешировать не имеет. Ну например обращение к переменной или числу.

При интерпретации списка инструкций у нас будет заранее созданный массив для кеширования. Теперь инструкции для этой функции выглядят как

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

После этого мы получаем уже явно более хороший результат:

Метод
Время (в наносекундах)

Subtitute
6800

Наша скомпилированная функция
330 (было 650)

Эта жа функция, написанная прямо в коде
430

В репе и компиляция, и интерпретация инструкций реализованы тут.

Читать  Южнокорейский бариста воссоздаёт культовые картины и иллюстрации поп-культуры на молочной пенке (14 фото + 2 видео)

LaTeX
Это известнейший формат записи математических формул (хотя и не только их!), который рендерится в красивые картинки. На хабре он тоже есть, и все формулы, которые я пишу, как раз написаны в этом формате.

Имея дерево выражений сделать рендеринг в латех очень просто. Как сделать это с точки зрения логики? Итак, у нас есть вершина дерева. Если это число или переменная, тут все просто. Если эта вершина, например, оператор деления, нам больше хочется Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой, чем Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой, поэтому для деления мы пишем что-то типа

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

Все очень просто, как мы видим. Единственная проблема, с которой я столкнулся при реализации такова, что непонятно, как расставлять скобки. Если мы просто на каждый оператор будем их пихать, то будем получать такую ерунду:

Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

Однако внимательный человек сразу (а не как я) заметит, что если их убрать совсем, то при построения выражения вида Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой, у нас будет печататься

Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

Решается просто, вводим приоритеты операторов а-ля
args[0].Latexise(args[0].Priority < Const.PRIOR_MUL) + «*» + args[1].Latexise(args[1].Priority < Const.PRIOR_MUL);

И вуаля, вы прекрасны.

Латексиризация сделана тут. И слова latexise не существует, я его сам придумал, не надо пинать меня за это.

Решение уравнений
Вообще-то, с точки зрения математики вы не можете написать алгоритм, который находит все решения какого-то уравнения. Поэтому нам хочется найти как можно больше разных корней осознавая недостижимость конечной цели. Тут две составляющих: численное решение (тут все максимально просто) и аналитическое (а вот это уже история).

Численное решение. Метод Ньютона
Он предельно простой, зная функцию Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой мы будем искать корень по итеративной формуле

Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

Так как мы все решаем в комплексной плоскости, можно в принципе написать двумерный цикл, который будет искать решения, а затем вернуть уникальные. При этом производную от функции мы теперь можем найти аналитически, а затем обе функции Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой и Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой скомпилировать.

Ньютон сидит тут.

Аналитическое решение
Первые мысли довольно очевидны. Так, выражение, корни уравнения Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой равны совокупности корней Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой и Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой, аналогично для деления:

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

Для синуса это будет выглядить чуть по-другому:
case «sinf»:
Solve(expr.Children[0] + «n» * MathS.pi, x, dst);
return;

Ведь мы хотим найти все корни, а не только те, что равны 0.

После того, как мы убедились, что текущее выражение — не произведение, и не прочие легко упрощаемые операторы и функции, нужно пытаться найти шаблон для решения уравнения.

Читать  Let vs const — что использовать?

Первая идея — возпользоваться паттернами, которые мы сделали для упрощения выражения. И на самом деле примерно это нам понадобится, но сначала нам нужно сделать замену переменной. И действительно, к уравнению

Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

не существует никакого шаблона, а вот к паре

Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

еще как существует.

Поэтому мы делаем функцию что-то типа GetMinimumSubtree, которая вернула бы самую эффективную замену переменной. Что такое эффективная замена? Эта такая замена, в которой мы

  • Максимизируем количество употреблений этой замены
  • Максимизируем глубину дерева (чтобы в уравнении Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой у нас была замена Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой)
  • Убеждаемся, что этой заменой мы заменили все упоминания переменной, например если в уравнении Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой мы сделаем замену Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой, то все станет плохо. Поэтому в этом уравнении лучшая замена по Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой это Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой (то есть нет хорошей замены), а вот например в Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой мы можем смело делать замену Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой.
  • После замены уравнение выглядит много проще.

    Полином
    Итак, первое, что мы делаем, мы делаем expr.Expand() — раскроем все скобочки, чтобы избавиться от гадости вида Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой, превратив в Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой. Теперь, после раскрытия у нас получится что-то типа

    Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

    Неканоничненько? Тогда сначала соберем информацию о каждом одночлене, применив «линейных детей» (есть в прошлой статье) и развернув все слагаемые.

    Что у нас есть о одночлене? Одночлен — это произведение множителей, один из которых — переменная, либо опетатор степени от переменной и целого числа. Поэтому мы заведем две переменных, в одной будет степень, в другой — коэффициент. Далее просто идем по множителям, и каждый раз убеждаемся, что либо там Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой в целой степени, либо без степени вовсе. Если встречаем бяку — возвращаемся с null-ом.
    бякаЕсли мы вдруг встретили какой-нибудь Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой, Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой и прочие штуки, в которых упоминается Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой, но не подходит под паттерн одночлена — это плохо.

    Окей, мы собрали словарик, в котором ключ — это степень (целое число), а значение — коэффициент одночлена. Так выглядит он для предыдущего примера:
    0 => c
    1 => 1
    2 => 3
    3 => 1 — a

    Вот, к примеру, реализация решения квадратного уравнения
    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;
    }

    Этот момент еще не доделан (например, нужно правильно сделать для кубических полиномов), но вообще происходит это тут.

    Обратная развертка замены
    Итак, вот мы сделали какую-нибудь замену типа Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой, и теперь нам хочется получить оттуда x. Здесь у нас просто пошаговое развертывание функций и операторов, типа

    Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

    Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

    Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

    Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

    Отрывок кода выглядит примерно так:
    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);


    Код этих функций здесь.

    Читать  Миллиардер ищет спутницу на Луну (и жену заодно)

    Все, конечное решение уравнений (пока!) выглядит примерно так

  • Если знаем ноль функции или оператора, отправляем Solve туда (например, если Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой, то запустим Solve(a) и Solve(b))
  • Найти замену
  • Решить как полином, если это возможно
  • Для всех решений развернуть замену, получив конечное решение
  • Если как полином оно не решилось и у нас только одна переменная, решаем методом Ньютона
  • Итак, за сегодня мы:

    • Ускорили работу скомпилированной функции благодаря кешу
    • Отрендерили в LaTeX
    • Решили небольшую часть случаев уравнений

    Рассказывать про численный подсчет определенного интеграла я наверное не буду, так как это очень просто. Про парсинг я не рассказал, так как получил критику по этому поводу в предыдущей статье. Идея была в том, чтобы написать свой. Но тем не менее, нужно ли рассказывать про то, как мы парсили выражение из строки?
    Проект тут.

    В следующей части…Если еще хоть кому-то интересно, попробуем усложнить решение уравнений, добавив кубическую и четвертую степени, а так же более умную сворачивалку. Может быть будем подбирать паттерны, ведь любой школьник решит

    Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

    Но только не наш алгоритм. Более того, может быть будет неопределенный интеграл (начало). Расширение числа в кватернионы или матрицы пока смысла не имеет, но как-нибудь тоже можно будет. Если есть конкретная идея для части III, напишите в личные сообщения или комментарии.

    О проектеТе, кто посмотрели код, могли заметить, насколько же он сырой и не отрефакторенный. И, разумеется, я буду рефакторить, поэтому основная идея этой статьи — донести информацию теоретически, и уж потом подглядывая в код. А еще приветствуются pull-реквесты, хотя наверное до wolfram.alpha нам все равно не добраться. Проект открытый.

    А вот парочка примеров того, что мы сегодня сделали
    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}

    Пишем «калькулятор». Часть II. Решаем уравнения, рендерим в LaTeX, ускоряем функции до сверхсветовой

    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

    Спасибо за внимание!
    Источник

    I heart FeedBurner