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 ()
Ответ на: комментарий от hobbit

Например, «дрюкер» в русском звучало бы, IMHO, гораздо гармоничнее, чем «принтер». Но так сложилось.

Оно ещё и логичнее, т.к. друк это славянский корень. В польском принтер – друкарка.

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

Вот, вы бритву как зовёте: «бритва» или «безопасная бритва»? Я, вот, пользуюсь первым вариантом, потому как обычные бритвы давно стандарт, а опасные — экзотика. Хотя изначально было наоборот, бритвой считалась штука, которой можно нарисовать на горле ещё одну улыбку. А для новых, безопасных бритв следовало использовать дополнительное уточнение.

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

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

Чтобы понять удобство S-выражений, надо ими пользоваться.

Если просто пользоваться, то к ним привыкаешь и становится очевидно, что (sin x) и sin(x) это два разных способа сказать одно и то же, разницы особой нету. А вот если упороться по defmacro, то разница внезапно есть и сильно в пользу лисповой записи.

Какие, собственно, есть альтернативы? Если строки клеить, а потом eval использовать, то пупок развяжется. А если работать напрямую с AST, то обычные языковые функции не умеют с ним работать и язык распадается на два независимых диалекта: один для макросов, один для всего остального. Оба-два варианта сильно хуже.

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

В испанском,к слову, компьютер - это ordenador (то есть, упорядочиватель, в буквальном переводе, с корнем orden - порядок).

В китайском - 电脑,[diàn nǎo], электрический мозг.

И ничего, живут как-то :)

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

В испанском,к слову, компьютер - это ordenador

Это они из французского взяли. А там это слово внезапно придумали в IBM для французского рынка.

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

К слову, если последовательно придерживаться принципа «кто придумал, тот и называет», то придётся вместо «компьютер» говорить «Digitalrechner». Потому как тут у товарищей немцев приоритет.

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

Вот, вы бритву как зовёте: «бритва» или «безопасная бритва»?

«Бритвенный станок» :)

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

Возможно. Однако, слово писарь сейчас воспринимается однозначно, так что на переходный этап надо различать.

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

Если просто пользоваться, то к ним привыкаешь и становится очевидно, что ~(sin x)~ и ~sin(x)~ это два разных способа сказать одно и то же, разницы особой нету. А вот если упороться по ~defmacro~, то разница внезапно есть и сильно в пользу лисповой записи.

Так, подожди. Кто-то пишет на лиспе и не трогает макросы? Не, ну можно, конечно. Но зачем?

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

друк это славянский корень

Немецкий. Оттуда же «дрючок» и «вздрючить».

В Беларуси в середине девяностых принтеры пробовали называть «друкарками», но потом все-таки отказались.

thesis ★★★★★
()
Последнее исправление: thesis (всего исправлений: 2)
Ответ на: комментарий от den73

что же пошло не так с латынью, для начала

Реформация.

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

Druck означае среди прочего ещё и «угнетение». А, я абсолютно уверен, первая человекообразная обезьяна взяла в лапы палку именно, для угнетения других обезьянов.

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

вышедшее из употребление старое слово «писец». Отлично подходит для данного изделия.

Есть не вышедшее, оригинальное, абсолютно соответствующее всем другим языкам - «печатник».

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

И что же пошло не так с латынью

Есть мнение, с ней случилась «скверная латынь».

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

Так что скажите спасибо, что по-русски компьютер — это компьютер

По-русски это «процессор» ☺️

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

Затем, что это вам, старпёрам, когда-то емакс зашёл. А если смотреть объективно, то он так себе. Кодиум по фичам лучше. И всё основное в нём естЬ, например, диалоги, команды, вводимые через терминал и их автодополнение. Емакс объективно теряет популярность, этот факт вы в корзину не выбросите, максимум можете закрыть на него глаза.

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

Тоже отличный вариант, мне приходило в голову ещё «печатка» (на совпадение значений с ювелирным украшением — забить. Мало ли в языке многозначных слов). Вообще, проблема не в отсутствии в данном случае какого-то идеального ответа, а в зажатости, закрепощённости айтишников. Надо разрешить себе творить (в том числе, творить фигню), использовать жаргон, придумывать и пробовать разные варианты. Удачные приживутся и войдут в литературный канон.

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

Мне ИИ придумывает новые слова. Интеграшки, заINTить, я правда, так и не понял, что последнее слово означает, скорее всего, «инкрементировать».

den73 ★★★★★
()

Ну показания сходятся...

gap> x := Indeterminate(Integers, "x");
x
gap> p := 2*x^11 - 34*x^10 + 102*x^9 + 34*x^8 - 102*x^7 - 34*x^6 + 100*x^5 + 66*x^4 - 172*x^3 - 136*x^2 + 70*x + 104;
2*x^11-34*x^10+102*x^9+34*x^8-102*x^7-34*x^6+100*x^5+66*x^4-172*x^3-136*x^2+70*x+104
gap> RootsOfUPol(p);
[ 13, 4, 1, 1, -1 ]
gap> 
gns ★★★★★
()
Ответ на: комментарий от den73

Кодиум в эпоху ИИ агентов со своими деревянными ИИ плагинами - прошлый век. Само IDE должно быть MCP клиентом, управляемым естественным языком. Чем современный emacs и является. С 32-ой версии там ещё фич посыпется...

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

Взял как-то Emacs в охапку Lisp и пошел вместе с ним извлекать квадратный трехчлен…

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

Емакс объективно теряет популярность,

Всё в порядке, это его нормальное состояние.

этот факт вы в корзину не выбросите

Не выбросим. Корзина забита по край разными современными-модными-молодёжными альтернативами emacs’а. Надо завести корзинку по-больше, чтобы и кодиуму нашлось местечко.

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

Объективно, платформа Eclipse была/есть отличная. По забавному стечению обстоятельств, редактор там оказался не очень (на не маленьких файлах тормозит), и архитектура такова, что даже в emacs втащить интерфейс к jupyter проще, чем в eclipse.

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

Жизнь живая — это процесс непрерывного творения фигни. Так работает эволюция. В том числе и в языке, включая английский. Словотворчество — непрерывный процесс, большая часть выхлопа от которого идёт на свалку. Неудачные варианты или же слова, оказавшиеся невостребованными забываются, а вот малый процент удачных и нужных обогащает нашу лексику. Если же запретить себе ошибаться, то развитие останавливается. Получим какой-то хуторской язык, на котором как корововам хвосты крутить обсудить можно, а для современной городской жизни он не предназначен.

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

Это лучше, чем нежизнь на кладбище. Вот, в Plan9 или A2 ни системд, ни электрона. И что? И ничего, пофиг. Помолчим.

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

и палка, и бить палкой, и печатать (т.е. получать оттиск).

Тогда претензия на немецкость не принимается. У них там свой источник.

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

Вот ты знаешь, я это слово применительно к матричным принтерам и использую :)

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

Дежурно напоминаю, что emacs — не редактор и не IDE, но дожившая до наших времён лисп-машина. На которой написано много разных приложений, включая и тектсовый редактор (или несколько). А вот «платформа отличная, но редактор не очень» говорит о том, что платформа тоже так себе.

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

заINTить, я правда, так и не понял, что последнее слово означает, скорее всего, «инкрементировать».

Очевидно же — привести к целочисленному значению.

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

претензия на немецкость

гораздо состоятельнее претензии на славянскость, тем не менее.

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

Освоение происходит постепенно. До макросов можно и не добраться. Можно пройти пару лаб в универе и решить, что лисп — это такое старперско-академическое ненужно для написания факториалов и задротских методов разворачивания списков. Можно пройти первые несколько глав из SICP и там тоже нету никаких макр. Можно вообще на лиспе писать в стиле продвинутого питона и прекрасно жить. Да и для всякой мелкой скриптоты (как я его использую (если считать кложу лиспом)) макры особо не нужны. Много есть вариантов.

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

Лучшее, что у меня было от квена 3.8 - «явательно терпируется» (видимо, калька с «explicitly tolerated»)

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

Так может это немецкое заимствование?

Ни drücken, ни drucken в викисловаре как славянское заимствование не указаны

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

У меня есть ответ на вашу инсинуацию, но он пока не готов к публикации. ;-(

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

slime - клиент swank. swank хорош, но у него могут существовать и другие клиенты. Я говорю про популярность emacs. Непопулярность общелиспа во многом проистекает из того, что нельзя кодить в VS Code, а надо осваивать emacs. В моём понимании емакс едва ли не сложнее языка - язык-то в общем-то достаточно простой.

den73 ★★★★★
()

корни многочлена над кольцом целых

Я так и знал, что лишп ни для чего полезного не предназначен.

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

А почему для Java, С и Питона выбор инструментов разработки есть и это нормально, а для CL - только емакс и вим? Сможешь обосновать, что это нормально и других инструментов быть не должно? Или, что то же самое, объясни, зачем новичку учить именно Емакс, а нельзя продолжать работать в своей любимой среде разработки. Что такого принципиально есть в Емакс, чего нет в VS Code? Любой нормальный новичок в этом месте первый раз задумается, а туда ли он попал.

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