Решение уравнения 4-й степени при больших коэффициентах

[Kesler]

Мне нужно находить корни уравнения $a_{0} \, x^{4} + a_{1} \, x^{3} + a_{2} \, x^{2} + a_{3} \, x + a_{4} = 0,$ где $a_{i}, x_{i}$ могут иметь размер до 16384 бит ($a_{i}$ – целые, а у $x_{i}$ учитывается только целая часть). Корни в общем случае не целые, но точно вещественные (мнимой части нет). При этом дробная часть корня не интересует, нужна только целая часть, но (и это самое главное) с точностью до единиц. Хотя само наличие/отсутствие дробной части тоже неплохо бы детектировать, т. е. хорошо бы находить 4 пары чисел $(x_{i}, f_{i})$, где $f_{i}$ указывает есть или нет дробная часть (число 0 или 1).

Как находить такие корни максимально быстро? Можно искать точные решения методом Феррари, но они в общем случае получаются монструозными (с корнями 3-й степени, мнимыми частями). Можно ли быстро вытащить из этих нагромождений корней целую часть? Вторая моя идея – искать корни методом Ньютона (касательных). Может кто-нибудь подсказать самое быстрое решение?

[novichok2018]

Есть оценки для границ корней. Пробежаться по этому интервалу с единичным шагом, нет?

[Kesler]

novichok2018, $x_{i} \in [1, 2^{2^{14}}]$. Перебирать все варианты сомнительное удовольствие.

[Andrey A]

Kesler в сообщении #1480985 писал(а):

... корни уравнения $a_{0} \, x^{4} + a_{1} \, x^{3} + a_{2} \, x^{2} + a_{3} \, x + a_{4} = 0,$

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

[iifat]

Kesler в сообщении #1481034 писал(а):

Перебирать все варианты сомнительное удовольствие

Ну, к примеру, ряд Штурма. И можно пополам делить.

[Dmitriy40]

Кроме чисто математических методов ускорения есть и другая засада: числа в 16К битов слишком близки к верхнему пределу представимых чисел x87 (и сильно превышают стандартный double), что может не позволить впрямую преобразовать числа в плавающую форму и применить обычную математику, придётся или использовать библиотеку работы с длинными (целыми) числами, или использовать свои форматы плавающей точки. И то и другое медленно. Потому можно подумать как максимально сузить область поиска корней, чтобы можно было пользоваться стандартными форматами чисел (хотя бы double) и не вылезать в 80К битные числа (как может быть $a_0 x^4$). Пусть даже с потерей точности, уж проверить (уточнить) корень можно и потом, в полноразмерных целых числах.

[Someone]

Есть же стандартные библиотеки для работы с числами неограниченной точности: NTL, GMP и другие. GMP, вроде бы, позиционируется как одна из самых быстрых.

[vpb]

Someone
Коллега, а не поделитесь какими-нибудь ссылками на тему, какие они вообще бывают, арифметики большой точности ? В смысле, ссылкой на какой-нибудь понятный текст, а не просто название программного пакета.

[Someone]

vpb в сообщении #1481541 писал(а):

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

Я в затруднении. Я ни в коем случае не специалист в программировании. Конечно, в университете я программирование изучал (в машинных кодах и в автокоде для М-20 и на языке Algol-60 — в конце 60-х годов прошлого века), а когда появился доступ к ЕС-1020, самостоятельно изучал FORTRAN-IV и ассемблер. Потом, по мере появления персоналок, понемногу программировал на разных вариантах Бейсика, на языке Рапира, на Паскале (фирмы Borland, в том числе Delpi разных версий), на разных вариантах ассемблера, на C++ (опять фирмы Borland, включая разные версии CBuilder). Профессионально программированием никогда не занимался, только немного для себя. Это я написал, чтобы Вы понимали, какой я "профессиональный" программист.
Из библиотек арифметики высокой точности экспериментировал с NTL (точнее, с WinNTL — версией для Windows) и с GMP. Обе библиотеки бесплатные и работают с числами произвольной точности, лишь бы они помещались в памяти компьютера.
WinNTL написана на C++, и я компилировал её в Си-билдере. Она имеет возможность подключить в процессе компиляции уже откомпилированную GMP и использовать её для ускорения вычислений, но имеет более понятный для меня интерфейс.
GMP написана на смеси C, C++ и ассемблера. Для компилирования использовал MinGW/MSYS. Перед компиляцией тестируется процессор компьютера, и в дальнейшем утилита make использует результаты тестирования для выбора наиболее быстрого кода из имеющихся вариантов. Есть возможность указать при компиляции целевой процессор (не обязательно тот, на котором происходит компиляция).
Обе библиотеки сопровождаются руководствами, в которых описаны определяемые типы данных и функции, которых там очень много (не только арифметические операции; числа с плавающей точкой произвольной точности тоже есть).
NTL (Number Theory Library): https://www.shoup.net/
GMP (GNU Multi-Precision Library): https://gmplib.org/

С другими библиотеками такого рода не сталкивался.

[iifat]

vpb в сообщении #1481541 писал(а):

ссылкой на какой-нибудь понятный текст

Ээээ... Вы что, Кнута не читали? Куда уж понятнее. Или последние писки науки интересуют?

[vpb]

Someone
Спасибо.

Я лично в программировании вообще очень плохо разбираюсь, так что в сравнении со мной Вы корифей.

Я на самом деле другое имел в виду. По IEEE-754 есть разные пособия, например M.L.Overton, Numerical computing with IEEE floating point arithmetic, и другие (самое известное --- Голдберга). В них пишут про саму арифметику, а про аппаратную часть, реализацию в разных языках и системах т.д. --- совсем немного.
Вот у меня был вопрос, где почитать аналогичные тексты, но про арифметику повышенной точности.

Но всё равно спасибо; наверное, в тех ресурсах, которые Вы назвали, есть какие-нибудь ссылки. (Ну и другие места, где можно покопаться по этим вопросам, тоже есть. Но я думал, что у Вас больше информации, а Вы, как я понял, больше с точки зрения программирования смотрите).

iifat в сообщении #1481605 писал(а):

Ээээ... Вы что, Кнута не читали? Куда уж понятнее. Или последние писки науки интересуют?

Нет, не читал, как ни странно. Разве что заглядывал. Действительно, это упущение. Надо почитать. Спасибо за совет. Хотя я всё равно не уверен, что там есть то, что меня интересует.

[svv]

(Оффтоп)

С уверенностью можно сказать, что человек, решивший все задачи Кнута, круче самого Кнута.

[Someone]

vpb в сообщении #1481610 писал(а):

Я на самом деле другое имел в виду.

Я, честно говоря, подумал, что Вам нужно написать программу, для которой требуется библиотека вычислений с высокой точностью. Но если у Вас интерес чисто теоретический и не очень глубокий, то действительно можно почитать для начала второй том "Искусства программирования для ЭВМ" Д. Кнута. Если этого не хватит, то специалисты, вероятно, что-нибудь подскажут.

[iifat]

(Оффтоп)

svv в сообщении #1481615 писал(а):

что человек, решивший все задачи Кнута

Ну, учитывая, что чуть не в самом начале идёт задача доказать неразрешимость $x^n+y^n=z^n$ в целых положительных при $n>2$ — пожалуй, да.

-- 02.09.2020, 09:09 --

vpb в сообщении #1481610 писал(а):

не уверен, что там есть то, что меня интересует

Ну, не вполне понял, что именно вас интересует, но там несколько алгоритмов, безотносительно железа и языка программирования. Как я понял, со времени написания разработаны и более быстрые алгоритмы (ну, или, стоит уточнить, асимптотически более быстрые).

[vpb]

svv в сообщении #1481615 писал(а):

С уверенностью можно сказать, что человек, решивший все задачи Кнута,

Нет, мои познавательные планы в отношении Кнута очень скромные ...

Someone в сообщении #1481617 писал(а):

Я, честно говоря, подумал, что Вам нужно написать программу, для которой требуется библиотека вычислений с высокой точностью. Но если у Вас интерес чисто теоретический и не очень глубокий, то действительно можно почитать для начала второй том "Искусства

Мой интерес действительно теоретический, однако не от неча делать. Я программ не пишу, но сейчас работаю над кое-какими численными алгоритмами. И в этой связи прикидываю, на какую арифметику еще, кроме стандартной IEEE, они должны быть рассчитаны. А иначе работа может оказаться "на деревню дедушке".

Книжек я по арифметике читал, но Кнут в их числе не был. Так, слегка заглядывал.

У меня еще, в связи с Кнутом, вопрос. Вы и уважаемый iifat его, как я понял, читали. Там приводится много программ на языке воображаемого компьютера MIX. Но что-то с этим компьютером и его языком мутно. Так я хочу спросить: а применительно к тому, что в Кнуте написано про арифметику, этот MIX существенно нужен, или можно им манкировать, просто соответствующие места пропускать ?