LINUX.ORG.RU

Находим корни многочлена над кольцом целых на ЛИСП

 


0

2

Интро

Видел тут скриншот, где чел показывает, как пользоваться 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.


Ссылки:



Проверено: hobbit ()

Таки зачем-то я написал об этом! Я хотел и я сделал!

lolkasosaka
() автор топика
Ответ на: комментарий от bread

Вот именно из-за таких гусар у нас на фирме все вместо «многочлен» говорят «полином». Хотя это одно и то же. (~~)

hobbit ★★★★★
()

Ничего не понимаю, но мне отрадно видеть такие статьи на ЛОРе. На душе тепло сразу.

mshewzov ★★★★
()
Ответ на: комментарий от hobbit

Использование Octave и Maxima в решении полиномиальных уравнений

многочленных уравнений.

Во всем мире говорят «полином» (от греческого poly nomen). Многочлен выдумал какой-то надмозг от математиков, видимо боясь за чистоту русского языка.

Lucky ★★★
()
Ответ на: комментарий от hobbit

вместо «многочлен» говорят «полином».

полиням
ням-ням-ням
если ты понимаешь о чем я

всё, теперь и второе слово безнадежно испорчено

olelookoe ★★★★
()
Ответ на: комментарий от Lucky

Многочлен выдумал какой-то надмозг от математиков

Буняковский «Лексикон чистой и прикладной математики».

Во всем мире говорят «полином»

В Японии говорят «такосики» например, а Китае «досянши». Все это кто?

no-such-file ★★★★★
()
Ответ на: комментарий от no-such-file

Спасибо ему за изобретательность и глубокое знание русского языка. Теперь у нас есть красивые определения:

Бином (двучлен) — это алгебраическое выражение, состоящее из суммы или разности двух одночленов (мономов).

Благо физики не поддались на провокацию, оставив Ньютону его бином. А то бы сейчас разговоров было.

Lucky ★★★
()

Но ведь есть julia - современное специализированное вычислительное воплощение лиспа, только с нормальным синтаксисом, поддержкой, типами, и при всём при этом, охрененно быстрая. Питон есть с sympy, тоже не хило кроет лисп . Наконец, есть хаскели которые сами себе алгебра. И всё это на порядок прямее и удобнее и просто живее, ещё бы на коболе с алголом написал.

zurg ★★
()
Последнее исправление: zurg (всего исправлений: 1)

Но всё же вопрос остаётся: как поживает режим для CL в VSCodium?

den73 ★★★★★
()
Ответ на: комментарий от zurg

Взяли бы и рассказали чем предложенные альтернативы по вашему мнению превосходят лисп. Только по-фактам, а не «современное», «прямее» и т.п.

ugoday ★★★★★
()
Ответ на: комментарий от Lucky

Мультипенисуальное уравнение?))

UriZzz ★★
()
Последнее исправление: UriZzz (всего исправлений: 1)
Ответ на: комментарий от bread

Гусары за последней партой, молчать!

Сидит плачет, саблю точит…

dimgel ★★★★★
()

Первый раз на моей памяти, лиспер выдал не распальцовку аля а вот в лиспе было бы в 10 раз лучше, а просто привёл пример использования. :-))) Сразу видно - новенький :D

vtVitus ★★★★★
()
Для того чтобы оставить комментарий войдите или зарегистрируйтесь.