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

А вот «платформа отличная, но редактор не очень» говорит о том, что платформа тоже так себе.

Лучше Emacs в качестве редактора может выступать разве что Vim. Блокнотики на электроне откровенно слабее.

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

Если было бы нужно, значит сделали бы. Но не нужно, потому что лучшее уже есть. Плодить жалкие подобия можно, но смысл? Лисперы же не растишки, чтобы по NIH синдрому упарываться.

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

А чё только на 100 поделил лисповое время? А то какая-то не уверенная «победа» лишпа над презренными, но нужными людям языками. Но и скорость именно языка так не оценивают, специально подбирая пример в свою пользу, может автор конкретной либы и не заморачивался оптимизацией. И про скорость лишпа я не утверждал ничего, на самом деле не плохо, всего, в среднем, в полтора раза отстаёт от юльки -https://benchmarksgame-team.pages.debian.net/benchmarksgame/box-plot-summary-charts.html. И откуда вылезло требование «не обвязка»? Лисп, так-то, тоже не фига не чистенький и сишечку внутрях дёргает. В state of the art юльки, в том числе, входит и способность кооперироваться с другими языками. Питоновские библиотеки, к примеру, практически бесшовно можно использовать.

zurg ★★
()
Ответ на: комментарий от C-xC-f

А почему S-выражения — это ненормальный синтаксис?

Для человеков? Я думаю, потому что с ранней школьной скамьи формульный парсер у всех в голове, на мертво настроен на инфиксную и/или постфиксную нотации. Машине - может и нормальный, поэтому и живёт он сейчас лишь в качестве внутреннего формата.

Почему он должен следовать маниакальному желанию делать всё «прямее», «удобнее» и «живее»?

Эээ, лол что, это как раз естественное и правильное желание, а вот маниакальность это, как раз, пытаться вопреки фактам и устоявшейся практике применимости, мучая себя и других, изгаляться с сишками, бейсиками, пёрлами, каким-нибудь фортом ну и, пардон, лиспом. Я вот даже и не имею ничего против лиспа, сам с интересом SICP проходил, но прогресс таки случился и люди сильно лучше научились язычки проектировать. И вот эта юлька всё сколько-нибудь полезное взяла и из лиспа: множественная диспетчеризация - в основе языка лежит, макросы, лямбды/ФВП- которые сейчас минимальный джентельменский набор для любого промышленного язычка.

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

А чё только на 100 поделил лисповое время?

Потому что лисп факторизирует за 1.8 секунд этот многочлен 100 раз, а ждулия за 7 секунд 1 раз. Допёр?

Лисп, так-то, тоже не фига не чистенький и сишечку внутрях дёргает

Чего он там дёргает? GC что ли лол?

Но и скорость именно языка так не оценивают, специально подбирая пример в свою пользу

Тебе любой другой многочлен показать? (норм звучит)

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

множественная диспетчеризация - в основе языка лежит

Что нельзя сделать обычную функцию. Спасибо, не надо

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

Что за жалкий лепет я только что прочитал? Считаете будто есть нечто лучше emacs’а? Докажите это. С фактами и логикой. Нет — так нечего и буквы тратить.

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

Я к тому веду, что хорошая платформа позволяет написать хороший текстовый редактор. Даже так: хорошесть платформы проверяется способностью написать хороший текстовый редактор (или несколько). Вот на emacs’е можно написать vi (есть же в мире извращенцы). Хорошая платформа, мощная. А если на eclispe нельзя, то, ну, не знаю, сочувствую, чо …

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

Для человеков? Я думаю, потому что с ранней школьной скамьи формульный парсер у всех в голове, на мертво настроен на инфиксную и/или постфиксную нотации.

Так для человеков или для школьников? Вы определитесь. За пределами четырёх арифметических действий есть много чего интересного. Хотел бы я посмотреть инфиксную форму записей для интегралов, логарифмов и прочих 𝚺 и 𝚷 для последовательностей.

прогресс таки случился

Товарищ, вы не на митинге. Если у вас есть какая-то конкретика, чем один язык превосходит другой — излагайте, не сдерживайте себя. А лозунги кричать дело пустое и бесполезное.

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

Не понял прочитанное, получается. Но это у меня случается %)

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

с ранней школьной скамьи формульный парсер у всех в голове, на мертво настроен на инфиксную и/или постфиксную нотации.

Ну, скажем, 2 + 2 я согласен, но 2 2 + на школьную программу не ложится никак. По мне так что польская запись, что польская запись мало отличются от инфиксной записи. Привычка вырабатывается минут за 5-10 от силы. Неужели это непреодолимая преграда для современных разработчиков? :)

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

Считаете будто есть нечто лучше emacs’а? Докажите это.

Ну тут сложно что-то противопоставить. Emacs и правда плохой блокнот. Много лишнего умеет, хоткеи не похожи на виндовые и браузерные. Не каждый осилит, короче.

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

cua-mode и будет контрол-ц/контрол-в.

А куда тогда слой уровня режима сползает?

Но я осуждаю это!

Та же фигня. К тому же M-w C-y проще нажимать :)

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

Для этого нужно знать про cua-mode сперва. А для этого в свою очередь нужно захотеть узнать. А для этого нужна мотивация. А откуда она возьмётся, если человек про emacs ничего не знает? К сожалению, идея, что хороший продукт сам себя продаёт, многократно опровергнута на опыте.

P.S. emacs-tutorial содержится в поставке emacs’a и доступен на родном языке. Его можно за 15 минут прочитать и освоить базовый emacs, затратив меньше времени, чем тратится впустую на доказательства, что emacs сложный и непонятный, но …

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

Согласен. Всё это жуткая маргинальщина.Но зато emacs хоть в wayland работает, в отличие от vs code :) Но может уже и поменялось это

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

Для меня даже моя среда, которую я сам написал руками ещё до ИИ - уже лучше ЕМАКСА, несмотря на баги, которые я так и не смог излечить. Перечисляю:

  • из коробки список недавно открытых файлов
  • несколько окон с результатами поиска
  • привычные кнопки из коробки
  • нормальная прокрутка
  • нет безумного поведения буферов при наличии нескольких рамок или окон, которые всплывают куда не надо
  • по горячим клавишам переключаюсь в любой инструмент без танцев с бубном
  • нет минибуфера, а вместо этого отдельное окно не на одну строку, а на сколько надо
  • лицензия не GPL, можно встраивать в закрытые приложения
  • в качестве скриптвого языка самой среды используется tcl/tk, т.е. можно рисовать окошки, графики и т.п. Не знаю, может и в Емаксе тоже можно, но я бы не хотел даже пробовать

Ну и дальше уже идут улучшения, а именно внутри тот же самый SWANK и плюс ещё пошаговый отладчик для SBCL с брекпойнтами, устанавливаемыми мышью. Да, тебе они может быть и не нужны, и это твоё личное дело. А мне они были нужны и я их сделал. Кроме того, и Лиспворкс тоже обладает этой фичей, так что ты не сможешь сказать, что она не нужна ни одному лисперу. Как минимум, разработчики лиспворкса - лисперы и они её сделали, значит сочли нужной. И мне она в жизни тоже пригождалась для работы. Я сейчас на лиспе не пишу и в обозримом будущем не собираюсь, хотя крайний раз я получал деньги за работу на лиспе в позапрошлом году и использовал этот проект. А то бы я уже напустил агентов на дальнейшее совершенствование этой среды.

Однако мне не нужно ничего доказывать тебе потому что у меня нет задачи, чтобы ты отказался от емакса. Кроме того, вообще само требование быть лучше откуда взялось? На вкус и цвет товарищей нет. Выбор инструментов во многом продиктован вкусом. Я просто обращаю внимание на то, что такая позиция - это одна из причин, почему лисп так непопулярен. Потому что в современном мире без емакса прекрасно можно жить.

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

Да что вы говорите? Список недавно открытых файлов и несколько окон одновременно? Я впечатлён … Если честно, не знаю, что тут ещё сказать. Удачи вам, счастья-здоровья, побольше деньжат.

само требование быть лучше откуда взялось?

Господь создал людей такими.

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

Я сам, естественно, запускать EMACS не буду, но дипсик сказал мне, что и по сей день список недавно открытых файлов надо включать в конфиге. Вот обоснуй предполагаемому новичку, почему все программы как программы и там это просто есть, а в Емаксе надо включать. В чём выгода? Хотя в общем и целом мне всё равно, думаю, можно свернуть обсуждения.

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

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

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

Друг мой, если вам охота поговорить с чат-гопотой, то с ней и разговаривайте. Я в сторонке постою, мне с людьми интереснее.

и там это просто есть, а в Емаксе надо включать

Наверное потому, что когда у тебя окромя встроенных возможностей есть несколько тысяч отдельных пакетов с расширениями, вываливать всю эту функциональность на человека нецелесообразно, да и просто невозможно. Нету на Земле таких мониторов, чтобы вместить одновременно всю предоставляемую Emacs’ом функциональность. Как-то так.

Кроме того, в данном конкретном случае, в силу более удобного подхода emacs к работе с файлами, нет нужды «закрывать» и «выходить» из недавно открытых файлов. Поэтому вместо «списка недавних файлов» есть открытые буфера. Переходи к нужному по C-x b. Тащить же свои привычки и костыли вам никто не запрещает, но и присоединяться нет желания.

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

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

Отчего же, приводите доказательства, обсудим. На то и форум. Пока что из доказательств с вашей стороны я вижу, что ваш велосипед реализует 0.00001% имеющихся в emacs возможностей. Извините, но это как-то не очень впечатляет.

единственная возможная причина, по которой список недавно открывавшихся файлов не включён по умолчанию

Понимаю, сложно поверить, но emacs разработан, чтобы было удобно тем, кто им пользуется. А у нас проблем реализовать нужное поведение нету. И потребностей реализовать костыли, решающие проблемы иных инструментов, тоже нету. Но если хочется, то см. пункт первый.

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

Понятно, мой пример тебя не убедил и ты нашёл возражение. Однако надо, чтобы оно работало не для тебя, а для новичков. Когда я был новичком, я нашёл этот режим и включил его. Но я до сих пор не знаю, почему во всех программах (даже с большими возможносятми, как кодиум, или, допустим, reaper, если мы вообще про другое) это есть по умолчанию, а в Емаксе это слишком страшно. Страшно - это когда человек приходит со своим синдромом утёнка, созданным сотней других программ, и тут оказывается, что емакс весь из себя такой нетрадиционный, что нужно оставить своё эго за порогом и заново учиться делать базовые вещи. Инвестировать в такой инструмент с налёта кажется тупо не выгодно. То, что ты дал ссылку на список пакетов - это вообще не аргумент, я туда даже не пойду смотреть, и никто не пойдёт. Если ты хочешь кого-то пересадить на свой емакс и на лисп, это тебе придётся доказывать, что емакс лучше, потому что среда по умолчанию на сегодня для новичков - это не емакс, а вскод. По факту я могу сказать, что и для лиспа, и для окамля у емакса лучше сделаны режимы. В чём тут причина - я не знаю. Однако в нашей команде мы официально рекомендуем плагин для vscode. Лично я сейчас не занимаюсь окамлем, но если я буду заниматься, то я поручу ИИ агенту допилить этот плагин, чтобы он не уступал плагину для емакса, и он это сделает. То же будет и с лиспом, хотя с лиспом я уже достиг ситуации, когда у меня есть всё нужное (ну ладно, 90% функционала SLIME, не 100%), и я свободен от необходимости держать в голове нетрадиционную логику емакса. Это я, у меня все-таки есть сколько-то месяцев стажа работы в Емаксе. Нормальные люди даже не будут глядеть в сторону емакса. А для моего начальства емакс наверняка был одной из причин, по которой они закрыли лисп-направление в нашей команде. Потому что когда надо зарабатывать деньги, платить людям зарплату за освоение экзотического языка + ещё экзотического редактора, который к тому же никто особо и не жаждет изучать - это проигрыш в управлении. Удачи.

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

И я тебе привёл конкретные примеры, чем меня емакс раздражал, и я так и не смог с этим справится (ни с собой, ни с емаксом). На это мне ответ ноль, ты это пропустил и опять требуешь доказательств. А почему ты это пропустил? Если ты игнорируешь конкретно мои претензии, то ты и претензии любого другого человека проигнорируешь. Т.е. емакс у тебя объявлен идеальным, а пользователь - нет. В сектах так работает, но секта емакса уже не та, что раньше. В общем, если хочешь продолжения разговора, то нужен ответ по существу на прошлые проблемы, которые решает даже мой велосипед. Пока что ответов ноль. Ответ, что список недавно открывавшихся файлов - это слишком сложно, я не принимаю, для меня это звуччит неубедительно. Максимум, что могу заподозрить - что на самом деле в этом списке есть подводные грабли, поэтму-то его и нельзя включить по умолчанию.

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

К тому, что в хобби-деятельности можно что угодно рассказывать про то, какие у тебя хорошие инструменты и какое вкусное пиво. Это нельзя измерить. Профессиональный успех - можно. Из тех, кто зарабатывал на лиспе рядом со мной и даже где-то вместе со мной, на данный момент осталось не более одного человека, да и то, я просто с ним давно не общался, может быть он уже тоже занимается другим. Это значит, что с лиспом что-то не в порядке. Если начать искать причину, то почему бы она нашлась и не в Емаксе. Если не искать - ну пиво вкусное, да.

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

Однако надо, чтобы оно работало не для тебя, а для новичков.

Почему мой основной рабочий инструмент, который я использую вот уже более 20 лет, должен рассматриваться не с точки зрения, как он облегчает мою жизнь, а с точки зрения новичка, который видит его впервые и, судя по всему, против своей воли? Мы языки программирования выбираем по их способности решать проблемы реального мира или по лёгкости написания хелловордов? В консерваторию рояль покупают, чтобы виртуозы могли показать класс, или чтобы на них удобно было чижика-пыжика с собачьим вальсом изобразить?

ты дал ссылку на список пакетов - это вообще не аргумент, я туда даже не пойду смотреть

--- Почему это ты считаешь emacs лучшим?
--- У него богатые возможности, вот, смотрите.
--- Да пошёл ты в жопу, даже смотреть не буду, мне плевать!

Вот и поговорили.

Если ты хочешь кого-то пересадить на свой емакс

Я? Я хочу пользоваться лучшим инструментом. Мне будет приятно если и другие люди разделят со мной эту радость. Но насильно вас осчаcтливливать? Это не для меня, пользуйтесь своими блокнотами сколько угодно.

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

Не должен. А почему новичок должен рассматривать его не с точки зрения своего опыта, а с точки зрения твоего? Ведь не только ты старше его, но и он моложе тебя, когда он был в твоём возрасте, когда ты начал осваивать емакс, появились и другие инструменты, которых тогда не было. Кто знает, что будет, если в эти новые инструменты вложить столько же усилий, сколько ты вложил в Емакс?

Список, который ты дал - да, он ни о чём. Потому что нужно как минимум сравнивать его с аналогичным списком для VSCode или для условного инструмента X. Сама по себе его длина никакого смысла не имеет. Ты же не утверждаешь, что у тебя длиннее - просто говоришь, что у тебя длинный (список). Мне неинтересно. Я не люблю емакс за конкретные вещи, которые в нём сразу видны. Их можно починить - ну так и сделайте умолчания нормальными, чтобы я не тратил всю жизнь на написание хорошего .emacs. Чтобы можно было просто начать работать и ничто не раздражало. Длиной списка эти раздражающие умолчания не компенсируются. Я перечислил, ты меня в общем-то первым делом туда же и отправил.

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