10. Получение формул в математике.
В разделе "Признаки делимости" реально мы получали формулы, а не вычислительный алгоритм.
Данная тема заслуживает особого внимания, хотя предлагаемое сейчас может казаться не очень впечатлительным. Пример с расширениями полей был выбран по трем причинам:
- все в каком-то варианте уже у меня имелось, поэтому демонстрация идеи не требовала больших затрат времени,
- не очень удачный пример с конечными полями, о котором я писал и говорил в своем выступлении на семинаре, показывал, что с данным примером суперкомпилятор благополучно справится,
- в конце концов, оказалось, что получающиеся программы все же можно пускать на счет (в этом примере).
Напомню немного теории и введу обозначения. Пусть i обозначает мнимую единицу, q2 - корень квадратный из двойки. Число i является корнем уравнения X^2 + 1 = 0 , число q2 - корнем уравнения X^2 - 2 = 0.
В описываемых программах многочлен задается набором своих коэффициентов в скобках, например, многочлен X^2 + 1 записываем как (1) (0) (1) , многочлен X^2 - 2 записываем так: (1) (0) ('-' 2) .
Если присоединить к полю действительных чисел число i , то получится поле комплексных чисел. Если к полю рациональных чисел добавить q2 , то получится множество чисел вида a + b q2, где a и b -рациональные числа, которое тоже будет полем (то есть в нем можно складывать, вычитать, умножать и делить).
Присоединение (добавление) элемента к полю носит общий характер, а процедура присоединения выглядит так. Рассматриваются многочлены с коэффициентами из первоначального поля и неприводимый многочлен, корнем которого является заданный элемент. В дальнейшем работаем с остатками от деления многочленов на неприводимый многочлен. Сложение и вычитание сводятся просто к сложению и вычитанию исходных многочленов. Для умножения умножаем два многочлена и берем остаток от деления на неприводимый многочлен. Деление определяется как обратная операция к умножению и реализуется при помощи алгоритма Евклида нахождения наибольшего общего делителя двух многочленов (имеется полная аналогия работы с целочисленными остатками).
Комплексному числу a + bi соответствует многочлен b X + a , числу a + b q2 - тот же многочлен b X + a .
Таким образом, для реализации операций в новом поле надо написать алгоритмы сложения, вычитания и умножения многочленов, алгоритм деления с остатком двух многочленов, модифицированный алгоритм Евклида.
При реализации этих алгоритмов нет нужды определять (фиксировать) исходное поле, достаточно задать имена функций арифметических операций. Например, Q_add, Q_sub, Q_mul, Q_div.
Если мы хотим получать только формулы, то на этом и останавливаемся. Если же есть желание получать работающие программы, то на последнем этапе подсоединим модуль, в котором описаны эти функции. У меня среди старых программ нашлась программа на рефале вычисления арифметических операций над рациональными числами (дробями). Я решил ее использовать, поэтому и выбрал такие названия (поле рациональных чисел принято всегда обозначать буквой Q жирное). Можно вместо этих функций выбрать операции над классами вычетов.
Замечу, что выбор i или q2 - это лишь два понятных всем примера. Можно брать любой неприводимый многочлен. Если мы хотим работать с корнем кубическим из двух, то рассматриваем многочлен X^3 - 2. Сумма корня квадратного из двух и корня квадратного из трех является корнем уравнения X^4 - 10 X^2 + 1 = 0 .
Что делает суперкомпилятор в этом примере ? Он компилирует функцию
<FPINT s.Oper (e1) (e2) (e.PX) > или <FPINT INV (e1) (e.PX) >,
где e.PX - неприводимый многочлен,
e1, e2 - операнды,
s.Oper - одна из операций: ADD, SUB, MUL или DIV.
Задавая конкретный многочлен, мы получаем операции, например, для комплексных чисел или для чисел вида a + b q2. Можно фиксировать дополнительно один из операндов или делать их равными, рассматривать частные случаи операндов и т.д. Можно получать алгоритм для одной из операций или же для всех сразу.
Отметим, что исходная программа formula.ref содержит много рекурсивных функций, но после фиксации неприводимого многочлена и операции получается одно предложение рефала, состоящее из последовательности обращений к арифметическим функциям.
Предлагаются следующие файлы данного примера:
- formula.ref - интерпретатор арифметических операций в расширении поля, с которым работает суперкомпилятор,
- q.ref - модуль, реализующий арифметику рациональных чисел, используется для демонстрационных пусков на счет результата работы суперкомпилятора,
- formulaN.mst - демонстрационные MST-схемы, N -номер схемы,(соответствует номеру примера),
- formula.bat - bat-файл, который организует полный цикл работы суперкомпилятора для одного примера, параметром служит N - номер MST-схемы, результирующая программа записывается под именем r_formN.ref
- r_form.bat - bat-файл, компилирующий и запускающий на счет программу r_formN.ref, параметр тот же (как правило, эта программа не готова сразу для компиляции).
- r_form0.ref , r_form1.ref , r_form2.ref - результирующие программы, подправленные или прокомментированные и готовые для пуска на счет.
Предлагается несколько демонстрационных примеров.
ПРИМЕР 0. Неприводимый многочлен - X^2 + 1, получаются комплексные числа. Задана функция INV - нахождение обратного элемента по умножению. Я прокомментировал подробно полученную программу и вставил конкретные числа для пуска на счет. form0.mst r_form0.ref
ПРИМЕР 1. Комплексные числа. Операция не фиксирована, поэтому суперкомпилятор строит четыре функции от двух аргументов - Add, Sub, Mul, Div (здесь неточность - рефальская функция одна, но она реализует четыре алгоритма). Я привел полученную программу к более читабельному виду и вставил предложения для организации демонстрационного пуска на счет (r_form.bat 1). form1.mst r_form1.ref
ПРИМЕР 2. Расширение поля рациональных чисел при помощи корня квадратного из двойки. Результирующая программа чуть поправлена и в нее вставлен пример для пуска на счет. form2.mst r_form2.ref
ПРИМЕР 3. Расширение рациональных чисел при помощи корня кубического из двух. Операция не фиксирована. Программа получается большая. form3.mst
ПРИМЕР 4. По сравнению с предыдущим примером зафиксирована операция нахождения обратного элемента по умножению для чисел вида a + a q , где q - корень кубический из двух, т.е. происходит процесс избавления от иррациональности в знаменателе. Можно получить алгоритм избавления от иррациональности в знаменателе от произвольного выражения вида a + b q + c q^2 - очень трудная школьная задача. При проверке алгоритмов я умножал ответ на знаменатель и получал 1. form4.mst r_form4.ref
Общее замечание ко всем примерам. Поскольку целью этой работы является рассмотрение возможности применения суперкомпилятора для получения математических формул, то не ставилась задача получения идеального программного продукта. Здесь возможны какие-то погрешности. К числу замеченных мною относится отсутствие анализа 0 при делении. Наличие указанного анализа привело бы к усложнению программ и уменьшению наглядности.