Находим корни многочлена над кольцом целых на ЛИСП
Интро
Видел тут скриншот, где чел показывает, как пользоваться Maxima (кажется) для данной задачи. Я хочу показать, как выполнить поиск корней многочлена в ℤ[x] используя библиотеку cl-polynomial для Common Lisp.
Для задачи понадобятся SBCL, emacs, qlot и slime (за настройкой обратитесь к документации). Чтобы запустить cl-polynomial, в директории библиотеки нужно выполнить в консоли
qlot install
qlot exec sbcl
Либо qlot install и в emacs открыть любой файл в директории библиотеки и запустить slime: M-- M-x slime и выбрать qlot. Далее, если хотите воспроизвести результат, можете выполнить в REPL всё то, что есть на скриншоте. Код из lor.lisp я залил на pastebin.
Для чего эта библиотека?
Эта библиотека умеет совершать над многочленами простые арифметические операции: сложение, вычитание, деление с остатком, нахождение НОД (и решение ур-я Безу, т.н. расширенный алгоритм Евклида). Также она умеет раскладывать многочлен на неприводимые сомножители. Всё это работает для многочленов над кольцом целых или для многочленов над конечным полем (но только с простым количеством элементов). Также для конечных полей есть алгоритм быстрого преобразования Фурье, так что можно перемножать многочлены быстрее, чем за O(deg f * deg g).
В отличие от maxima, это именно библиотека, а не standalone программа без API.
Что происходит на скриншоте?
На скриншоте мы находим корни многочлена $2x^11 - 34x^10 + 102x^9 + 34x^8 - 102x^7 - 34x^6 + 100x^5 + 66x^4 - 172x^3 - 136x^2 + 70x + 104$.
Можно выполнить эту задачу, разложив его на вообще все неприводимые сомножители. Несколько перебор, но почему бы нет?) Для этого в библиотеке есть функции factor в пакетах zx и fpx (я немного сократил названия пакетов, опустив префикс cl-polynomial/). Первая — для кольца целых, вторая — для конечных полей. Обе функции дают 2 значения: первое — список неприводимых сомножителей вместе с их кратностью, второе — контент многочлена (я не знаю русский термин). Перемножив их все с учётом кратности, получим исходных многочлен.
Пользуясь этим, функция demo:roots находит сомножители первой степени и, вычисляя их в 0, находит корни многочлена. Функция demo:rootsp делает проверку, подставляя корни в многочлен и убеждаясь, что в результате будет 0.
Таким образом, у многочлена, записанного выше, есть корни -1, 4, 13, 1.
Ссылки:


