Комментарии 49
Перестановка порядка действий плюс ошибки вычисления в последнем знаке могут привести к потере устойчивости решения.
A = a/ĕ - a*(1/ĕ), ĕ->0
А у вас ещё и динамически неустойчивые системы.
Извините, теорию уже не помню
Всё что могу
Хотя программирование и не моя специальность
После вашей статьи даже как-то неловко теперь себя называть программистом
Есть! Есть еще программисты у нас в стране! Спасибо за статью.
Задача интересная, но тема готовых решений не раскрыта. Maxima не удовлетворила, но что с другими решениями? Sympy для Python, simplify для MatLab/Octave, например?
Ощущение -- как от статьи про устройство БАКа (котороый коллайдер). Т.е. понятно, что это что-то большое, интересное и могучее, но остается вопрос: А как бы это применить, грубо говоря, у себя на кухне?
Например, можно ли это применить для расчета диффузии сигнальных молекул в межклеточном матриксе, чтобы понять, как клетки общаются друг с другом? Или лучше использовать какие-то более простые инструменты?
В принципе, эта штука универсальная, можно для любых уравнений применять. Конкретно диффузией (кроме очень специфических случаев) я не занимаюсь, поскольку в моих задачах диффузия почти не имеет значения. Что касается молекул -- я очень далек от этого, но знаю, что задача очень сложная, потому что даже спектры молекул, кроме простейших, до сих пор невозможно строго рассчитать, что уж тут говорить о диффузии. Скорее всего там применяются какие-нибудь полу-эмпирические модели, основанные на данных из натурных экспериментов.
Огромное спасибо за статью! Технические подробности это прям глоток свежего воздуха в нынешней информационной пучине, как будто Стругацких почитал.
Хотелось бы увидеть завершение статьи, на самом деле. Хорошо показан переход от задачи к решению, но обратного перехода нет - как решение встроилось в задачу? Удалось ли приложить это к большим вычислениям? Привело ли это к экономии времени?
Ну и да, приятно что такой человек вообще существует. Занимается наукой, самостоятельными исследованиями новых областей, технической реализацией, и даже вот статью написал. Спасибо ещё раз!
SymPy это хорошо умеет: https://docs.sympy.org/latest/tutorials/intro-tutorial/simplification.html
Спасибо!
Общеупотребимое название для процесса extract-nums — частичные вычисления. Вообще, вся эта машинерия напоминает оптимизирующую часть компилятора, и, видимо, является именно ею. :-)
Возможно, вы можете ещё почерпнуть вдохновения из заметок про Суперкомпиляцию (Надкомпиляцию) https://sergei-romanenko.github.io/scp-notes-ru/
И так, пока выражение не перестанет изменяться.
Это называется «достижение неподвижной точки». :-)
Спасибо за ссылку, обязательно почитаю! Это действительно часть "компилятора", довольно специфического, который нужен был мне для своих специфических задач. Там еще довольно много велосипедов, я подозреваю, я изобрел, когда писал оптимизатор, но об этом уже в следующей статье)
Кстати, ваша задача напоминает так называемую «ярусно-параллельную форму» графа. Эти формы и соответствующие алгоритмы встречаются у VLIWщиков.
У меня всё немного проще, параллелизм в алгоритме явный. Я просто изобрел (или думаю, что изобрел) несколько приемов, позволяющих выжать CPU и GPU "досуха" на моих задачах. Спойлер: это вышло мне боком, так как при полной загрузке сразу двух GPU на тестовом сервере он банально зависал, чего не наблюдалось, когда производительность выжималась не полностью)
Вроде как раз лет двадцать тому гремели холивары, а не стоит ли плюнуть на все это якобы фришное и продать душу Вольфраму. С тех пор производитеьность и инструментарий Mathematica несколько подросли, хотя и хаоса и непредсказуемости прибавилось.
Но я бы, встретившись с векторизуемым алгебраическим монcтром, попытался подсунуть его в Mathematica. Вероятно -- рухнет, или сожрет всю память, а потом рухнет. Но зачастую прокатывает.
Вы потихоньку создаете аналог Mathematica. Которая тоже основана на lisp-подобном функциональном языке.
Ну, не всю Mathematica, только очень маленькую ее часть, нужную для моих нужд. Лисп очень часто используется для символьных вычислений, чему есть причины)
Я решал похожую задачу, правда, в квантовой теории поля, как раз с помощью Mathematica. Встроенная функция FullSimplify работает хорошо только с простыми выражениями. Если запихивать в неё какую-нибудь трехэтажную крякозябру, то надо заниматься тем же, чем уважаемый @Hemml занимался в своей работе: поиском шаблонов, рекурсивной подстановкой, указанием типов всех констант и переменных, оптимизацией к неподвижной точке и т.д. Да ещё и скорость всего этого добра оставляет желать лучшего. И синтаксис там ужасный :)
Вообще говоря, задача упрощения не поставлена до конца — нельзя сказать, что мы про любые эквивалентные формы можем договориться «что проще». То есть, в любом случае, есть даже простор для творчества в постановке, не говоря уж о других специфических вещах.
Конкретно в моем случае ставилась задача сократить количество вычислений, убрав ненужные.
Это у всех так: добавить нужное, убрать ненужное. Дело в том, что нужное для всех разное. То есть, на мелких деталях появляются различия между разными задачами упрощения. И в общем виде учесть можно только грубые вещи, вроде умножения на 0.
Например, для старых сопроцессоров 
будет вычисляться проще, чем 
, а что проще для человека?
Или возьмите выражение 
, сравните с 
. Какое из них будет «более простым»? А могут быть ещё более забубенные вещи с логарифмами:
Вот что тут «проще» — левая или правая части? На эту тему была статья, кажется у Вольфрама, но я её читал пару десятилетий назад. И там, если я правильно помню, дело сводилось к каким-то эвристикам, к каким-то «общечеловеческим представлениям о прекрасном».
Вот, собственно, еще одна причина, по которой я взялся писать свою символьную математику. У меня была задача -- максимально ускорить вычисления. Я бы взял разные варианты упрощения и настроил бы свою процедуру так, чтобы она давала наиболее быстро вычисляемый вариант. Даже если бы результат для человеческого глаза был бы не самым простым. Отчасти, это уже сделано, возведения в не слишком большие степени моя библиотечка заменяет на умножения, например. Еще я хочу добавить учет точности, чтобы можно было задать предельную точность при которой числа считались бы равными. Это позволило бы выносить за скобки близкие но не равные константы, например. Да много чего еще можно добавить, если у тебя есть контроль над модулем символьной математики!
Или возьмите выражение
Эти формы еще и на результат могут влиять. Но, с учетом того, что у автора в приоритете скорость, а не точность, то особо так важно.
Кажется, здесь нужно использовать веса для различных функций. Например, логарифм намного сложней умножения или деления, так что вес у него больше и записи справа проще в данном контексте. Хотя если умножений много, а логарифм - один, то логарифм оптимальней. Все это неточно и может работать неправильно на каких-то краевых случаях.
В целом я согласен - задача упрощения выражений довольно расплывчатая и сложная. Скорей всего у идеального алгоритма такая сложность, что она делает его непрактичным для реального использования и без эвристик не обойтись.
Ага, так что даже при использовании существующих математических пакетов приходится писать кучу кода под конкретную задачу. Причём он будет плюс-минус одинаковый вне зависимости от базового пакета: шаблоны, типы, костыли.
Чтобы проверить, эквивалентны ли выражения
и
, нужно просто упростить левые части следующих выражений и проверить их истинность:
Кажется здесь даже не надо вычислять ни вычитание, ни деление. Правильней было бы нормализовать выражения (упростить и отсортировать внутренние слагаемые). Затем вычислить хеши, если они равны, то уже произвести сравнение деревьев этих выражений.
Я, кстати, над подобным проектом занимался, правда это было более 10 лет назад, может полезно будет: Математические выражения в .NET (разбор, дифференцирование, упрощение, дроби, компиляция)
Один разбор этого выражения (а ведь в нем тоже могут быть скобки! И некоторые из них, но не все, ограничивают параметры функций!) может стать темой дипломной работы, чего уж тут говорить об удобстве.
Это к теме формальных грамматик и парсинга. Там могут быть какие-то сложности, неоднозначности, но в целом не должно быть особо сложно.
В лисп же первый член списка это всегда обозначение функции, а все остальные - ее параметры. В общем, если вам нужно работать с символьными выражениями, выбирайте лисп, не пожалеете.
Это удобно с точки зрения синтаксического разбора, но с точки зрения восприятия инфиксная запись формул все-таки удобней для восприятия человеком.
Кстати, а вы солверы не смотрели? Например, Z3. Для описания моделей в нем тоже используется lisp подобный язык, есть функции упрощения, а для кастомных правил есть такая фича, как тактики.
Синтаксис дело привычки, мне на первых порах тоже было неудобно, а потом наступил момент, когда я на инфиксную запись уже смотрел с неодобрением) В лиспе формулы представлены в естественном виде, с которым удобно работать, ведь меня не сама формула интересовала, а генерация кода из нее. В случае работы со строками мне сначала пришлось бы составлять строку, потом парсить строку вывода в какой-нибудь внутренний формат, который бы подозрительно напоминал лисповый список с префиксной формой внутри. Так почему бы не работать сразу со списками?
Что касается солверов, то, вполне возможно, что их получилось бы использовать, но для этой задачи они немного оверкил, мне кажется. К тому же 15 лет назад, когда я начинал этот поход, вряд ли они были доступны.
Синтаксис дело привычки, мне на первых порах тоже было неудобно, а потом наступил момент, когда я на инфиксную запись уже смотрел с неодобрением)
Я тут имею в виду скорей ситуацию в общем. Например, математики издавна пользуются инфиксной формой, так и не перешли на lisp-подобный формат. Хотя у них в формулах вообще намного больше визуала, но это все равно ближе к инфиксной записи.
В случае работы со строками мне сначала пришлось бы составлять строку, потом парсить строку вывода в какой-нибудь внутренний формат, который бы подозрительно напоминал лисповый список с префиксной формой внутри.
Да - это называется деревом разбора.
Так почему бы не работать сразу со списками?
Да, это валидный аргумент.
Например, математики издавна пользуются инфиксной формой, так и не перешли на lisp-подобный формат
Это вопрос традиции. Из-за которой, например, у математиков плюс и знак суммы изображаются по-разному, хотя это по существу (и в Лиспе) одно и то же. Но когда математикам приходится работать именно с синтаксисом выражений, как с исследуемым объектом, то тут же никаких инфиксных форм не остаётся, а появляются лямбда-выражения и прочие операторы.
Вы свернули не в ту сторону. Почитайте про методы оптимизирующих компиляторов и symbolic execution. И вынужден огорчить: разбор выражения это не тема дипломной, а лишь практическая работа на третьем курсе =)
Очень интересно!
Мне нравится Maple, но как-то столкнулся с тем,что 12-я версия упрощала крокодилистые выражения как нужно, а более свежая - увы нет.
Я тут пробегал кабанчиком... большое уважение за статью, очень интересно и вообще это полезно для человека реализовавшего это, но вы не пробовали в своей работе вот это:
FullSimplfy
Simplify
Expand
Factor
TrigExpand
... и т.д.
Я принципиально не хотел быть завязанным на внешний сервис. Даже локальная Maxima вызывала у меня некоторую степень дискомфорта. Да и Вольфрам, начни я ему скармливать в автоматическом режиме уравнения на тысячи членов, скорее всего забанил бы меня очень быстро. По крайней мере, я бы на его месте так и сделал)
Какой сервис? О чем вы говорите? О Wolfram Alpha? Можно поставить бесплатный Wolfram Engine и пользоваться для личных целей сколько угодно. А при желании можно на него накатить еще и WLJS
Я не знал про Wolfram Engine, спасибо. Но, судя по всему, он появился только в 2019 году, то есть лет через 5 после большей части описываемых в статье событий. К тому же у него довольно ограничивающая лицензия, мне всё равно пришлось бы менять его на что-то другое, в случае, если бы исходный проект выстрелил.
Ну так Mathematica была такой же, тока за деньги и с UI. И появилась в 1988. Wolfram Engine конкретно сейчас дает возможность создавать приложения на WL
Я сначала думал это может быть я что-то пропустил, но пересмотрел еще раз и не нашел никаких упоминаний в самой статье в каком году вы делали библиотеку. После этого вы во всех комментариях всем отвечаете «это же было 15 лет назад, зачем вы мне советуете современные инструменты!»
Что касается Scheme, то существует неплохой компилятор в Gambit. Не возьмусь, однако, его сравнивать с SBCL.
Упрощать сложно. История одного провала