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

[svv]

Листал.
Я не поддерживаю Д.Кнута в выборе MIX как средства записи программ. Это такой ассемблероподобный язык, с явным обращением к регистрам, собственное творение автора. И то, и другое свойство для меня — минусы. С другой стороны, автора можно понять. Использование языков высокого уровня влечёт потерю эффективности, а в книге про самые-самые оптимальные алгоритмы этого допустить никак нельзя.
Совсем всё пропускать, что написано на MIX — тоже не вариант, боюсь, это всё равно, что пропускать все формулы. Но и вгрызаться в каждую программу не имеет смысла.
Т.е. кратко — «не знаю».

[vpb]

svv
Понятно. Ну, подождем мнений других коллег ...

[Someone]

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

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

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

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

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

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

[vpb]

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

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

Это понятно. Я в этом и не сомневался. Но, как Вы все же считаете, знать этот MIX критично, чтоб понимать главу про арифметику во втором томе, или можно обойтись ?

-- 02.09.2020, 20:20 --

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

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

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

[Dmitriy40]

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

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

Обращу внимание vpb на выделенное жирным слово, это принципиальный момент. Пока пишете алгоритмы на С/С++ и прочих языках более-менее высокого уровня, всё хорошо. Но действительно высокопроизводительные решения используют специфические особенности аппаратуры (например SSE и AVX в случае x86) и вот тут поджидает засада, они очень плохо переносятся на другую аппаратуру. Потому часто ради производительности жертвуют совместимостью и пишут варианты под каждый вариант аппаратуры свой код (по крайней мере функций нижнего уровня). Так кстати поступают и в GMP.
Глянул я её кстати, очень мельком, не тесты общей производительности, а очень отдельный вопрос извлечения квадратного корня из длинного целого числа. Ну, там классический Ньютон, с длинными делениями, мрак. Надеялся хотя бы через обратный корень сделали, без делений, ан нет. Но возможно посчитали маловажной операцией (что странно!) и ради универсальности (корень любой целой степени) не стали тратить ресурсы на оптимизацию квадратного ...

vpb
Что ещё сказать, Кнут конечно могуч, и если хотя бы часть Ваших алгоритмов у него рассмотрена или Вы можете свести что-то своё к рассмотренному им, то это стоит сделать. Не обращая внимание на MIX, сравнивая лишь асимптотики (правда очень аккуратно и внимательно, лучше даже по каждым типам операций отдельно), всё же MIX достаточно похож на любой современный процессор чтобы не иметь существенных проблем при выполнении на реальном железе. Это первое.
Хотя существенные отличия всё же есть, самое известное из которых наверное наличие кэшей (если не ошибаюсь про MIX, давно не заглядывал), они сильно влияют на некоторые алгоритмы (где используется много памяти).
Второе, если в каком-то Вашем алгоритме понадобилась арифметика повышенной точности или вообще с любым отличием от стандартной IEEE (а их много может быть, этих отличий), то оцените даваемый алгоритмом выигрыш, пересилит ли он замедление всех элементарных операций с числами, последнее можно взять из тех же тестов скорости GMP (или грубо оценить как замедление на порядок для небольших чисел или околоквадратично по длине чисел для длинных). Потому что без аппаратной поддержки любая арифметика будет медленной.
Третье, имеет смысл разрабатывать две версии алгоритма, универсальную и специфичную с большим выигрышем скорости, подробно оговаривая какие именно операции требуются для последней. Может кто-то захочет потом написать их на ассемблере под конкретный процессор или вообще разработают FPGA или даже вдруг включат такие операции в следующие версии процессоров ... Это не такая уж фантастика: AES, CRC, видеокодеки, битовые операции уже прошли этот путь. Главное чтобы выигрыш был на порядок (порядки) и алгоритм достаточно востребованным.
Четвёртое, не стоит повторять GMP и прочие, используйте их (в принципе любую, какая покажется проще и удобней). Сосредоточьтесь на своих алгоритмах, а не деталях реализации арифметики, если они не сильно мешают.
Пятое, уж извините за кучу общих слов без конкретных ссылок, но лично мне ближе ассемблер и вопросы оптимизации на языках высокого уровня интересны "для общего развития".

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

знать этот MIX критично, чтоб понимать главу про арифметику во втором томе, или можно обойтись ?

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

[Someone]

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

знать этот MIX критично, чтоб понимать главу про арифметику во втором томе… ?

Ни в коем случае. Тем более, что программ на языке MIX в этой главе практически нет.

[vpb]

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

Ни в коем случае. Тем более, что программ на языке MIX в этой главе практически нет.

Dmitriy40 в сообщении #1481773 писал(а):

Я считаю вполне можно обойтись,

Спасибо. Я, в общем, примерно так и думал. Теперь в случае чего не буду себе голову морочить.

(Тем временем, я обнаружил, что описание MIX является, кажется, менее мутным, чем мне показалось. Более точно. В Кнуте есть примеры "арифметических команд с упакованными числами", вот это и есть локально мутное место, которое меня сильно смутило. Я даже поискал по зарубежным ресурсам, так там тоже люди в ступоре: мол, читаю Кнута, что в этом месте за фигня написана ?)

Dmitriy40
Спасибо за большой ответ, но, так сказать, разработка высокопроизводительных программ, учитывающих особенности конкретных машин --- это от меня весьма далеко. Да и на языках высокого уровня (точнее, на Си, других-то не знаю) тоже не пишу. Рассматриваю алгоритмы теоретически, и оцениваю не по времени исполнения в секундах, а по числу операций. А главное --- с точки зрения численной устойчивости. Так сказать, в духе Уилкинсона, а вовсе не Кнута. То есть и Кнута тоже, но в малой степени. Как-то так. А воплощение и использование, буде у них будет такая нужда, остается другим специалистам, если они невзначай на мою работу (ненаписанную еще к тому же пока ... ) в журнале или Архиве наткнутся.

[iifat]

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

просто соответствующие места пропускать

Ну, вам тут, собственно, уже всё ответили. Думаю, для понимания алгоритма (да и вообще) язык Кнута не нужен (имхо, вообще в книге не нужен, но кто я такой чтоб спорить с Кнутом). Тем более что, как понимаю, и алгоритмы эти только для ознакомления — вроде б, пара-тройка были разработаны и после написания книги.

[Dmitriy40]

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

Рассматриваю алгоритмы теоретически, и оцениваю не по времени исполнения в секундах, а по числу операций.

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

(Упакованные числа)

Сначала подумал про другое, про BCD числа, но у Кнута это кажется всего лишь не слишком ясное выражение того факта что куча битов в слове могут рассматриваться или как одно число, или как два числа, или как три, или ... — и некоторые операции во всех (или некоторых) этих вариантах выдают осмысленные результаты. Правда внимательно разбираться не стал.

[dmd]

pari/gp поддерживает GMP.

Функция polrootsreal считает неким Uspensky's method:

? ?polrootsreal
polrootsreal(T, {ab}): real roots of the polynomial T with real coefficients, using
Uspensky's method. In interval ab = [a,b] if present.

Тестовый код для вычисления 4-х корней тысячи уравнений со случайными коэффициентами заданной размерности:

eq4r()=
{
 q= 0;
 while(q<1000,
  t= 2^16384;
  a0= (-1)^random(2)*random(t);
  a1= (-1)^random(2)*random(t);
  a2= (-1)^random(2)*random(t);
  a3= (-1)^random(2)*random(t);
  a4= (-1)^random(2)*random(t);
  f= a0*'x^4 + a1*'x^3 + a2*'x^2 + a3*'x + a4;
  if(polsturm(f)==4,
   q++;
   X= polrootsreal(f);
   write("eq4r.txt", "\na0 =\n"a0"\na1 =\n"a1"\na2 =\n"a2"\na3 =\n"a3"\na4 =\n"a4"\n");
   for(i=1, #X,
    write("eq4r.txt", "x"i" =");
    write("eq4r.txt", floor(X[i]))
   );
   write("eq4r.txt", "\n\n\n")
  )
 )
};

Посчиталось и записалось в файл за пол-минуты. Сделал выборочную проверку нескольких посчитанных уравнений в Вольфраме - считает верно.

[vpb]

Всем высказавшимся по моему вопросу еще раз спасибо. Почитаю Кнута, в самом деле.