Comments 13
умножение это операция порождающая связность битовых разрядов (в принципе имеющая матричную природу) - все упрощения умножения полиномов будут алгебраически иметь ту же природу что и методы быстрого умножения матриц. А потому построение вычислений на независимых операциях умножения это строго в противоположную сторону оптимизация. И короткий ответ нет нельзя.
Однако это не касается длинной арифметики - если вы вычисляете что-то где единственный операнд представляется в виде массива данных, то там есть методы реализации длинной арифметики, которые часть вычислений могут выполнять независимо, за счет чего ускоряться. - НО это по сути не относиться к алгоритму самого умножения полинома
если вы говорите про float вычисления, то при сокращении числа умножений средне ожидаемая ошибка будет тоже сокращаться. Так что скорее более точный получится. Количество же сложений не имеет значения, потому что ошибка на них (имеющаяся и в схеме Горнера) может в обоих случаях вычисляться алгоритмом компенсационного суммирования Кэхэна. ну и если надо абсолютно точно то вы обычно берете длинную арифметику - которая уже только ускорятся будет от использования более оптимизированных схемм
В 1999-2000 учебном году ему [преподавателю] впервые поручили вести лекции. Он вёл их препаршиво. На пресс-конференции, связанной с днём факультета:
Студент: Вы видели когда-нибудь компьютер?
И.И.: Конечно. Вот я помню машину XX-XX, 2-го поколения. Я бы её не променял даже на вагон персоналок.
Вмешивается декан: Ведь эта машина работала на спирту.
Что это за машина и почему «работала на спирту»?
А вот я еще недавно наткнулся на следующую схему вычисления полиномов, не требующую умножений, если полином требуется вычислить в равноотстоящих точках.
Идея — в составлении системы разностных уравнений и их решении в прямом времени. Для этого требуется только сложение. Так, для полинома первой степени y = a1x+a0
y(x+dx)-y(x) = a1dx, где dx — интервал между точками, в которых требуется вычислить полином. Так как a1 и dx — константы, то умножение требуется выполнять только один раз.
Для многочлена второй степени y0 = a2x^2 + a1x + a0 имеем:
y0(x+dx)-y0(x) = a2(x+dx)^2 + a1(x+dx) — a2x^2 — a1x = 2a2xdx + a2dx^2 + a1dx
Здесь в правой части имеется константа и функция 2a2xdx. Но это многочлен первой степени, который мы уже умеем вычислять в равноотстоящих точках. Назовем его y1(x) и составим для него разностное уравнение:
y1(x+dx)-y1(x) = 2a2dx.
В конечном итоге получаем систему из двух разностных уравнений:
y0(x+dx)-y0(x) = y1(x) + a2dx^2 + a1dx
y1(x+dx)-y1(x) = 2a2dx
Эту систему можно легко решать в прямом времени. В правой части каждого уравнения у нас имеются только константы, которые надо прибавлять, и значения других переменных, которые мы получаем в ходе решения системы.
Аналогичным образом для многочлена третьей степени можно составить систему из трех линейных разностных уравнений, для четвертой степени — систему из четырех уравнений и т.д. Один шаг решения каждого из уравнений — добавление константы, поэтому решение всей системы (вычисление всего полинома в следующей точке) нам обойдется во столько сложений, какова степень этого полинома.
Если все константы и начальные условия выражаются целыми числами — то решение будет точным.
Именно таким образом был получен лучший алгоритм для вычисления таблицы синусов на ZX Spectrum на форуме zx-pk.ru. Синус был приближен полиномом 3-й степени, который вычислялся по приведенному выше алгоритму. Размер программы и точность оказались рекордными среди предложенных вариантов.
Кстати говоря напишите где по этому методу вы встречали теорию, если помните...
Я этот метод открыл независимо, и практикую.
И он мне кажется настолько крут, что я чувствую необходимым по нему писать подробную статью на Хабр. Ощущение, будто я рискую общечеловеческим достоянием пока не отписал (ибо смертен)
Однако такой материал находиться на стыке математики и программирования. А я в математике самоучка и терминологически подкован плохо. Знаю как работает, но как популярно объяснить испытываю трудности. Если существует какая-то математическая терминология на этот счет на нее очень было бы полезно сослаться.
Кстати говоря мало того что, метод требует только сложений, они в нем с т.з. параллелизма еще и все НЕзависимые!
что как бы говорит о том, что вычисления полинома N-ой степени на суперскалярной архитектуре, количество параллельных сумматоров в которой может вместить все коэффициенты (А их сейчас в среднем по 3 на ядро, при среднем количестве ядер = 4 это 12 штук) может вычислять полином степени на единицу меньшей чем их количество ЗА ОДИН ТАКТ!!!
И даже это еще не все... на самом деле независимость сложения позволяет продемонстрировать это в еще более дерзкой форме, т.к. по сути для этих вычислений важна скорее общая битовая размерность сумм. И если скрестить это с битхакерскими техниками группировки разрядов в одну переменную, то можно параллельности добиться на однопоточной машине и без супперскалярности, просто используя младшие биты результата. Следующий пример на JS вернет параболу (полином 2й степени) используя на точку только одно сложение ui32 числа со своими же старшими разрядами
let x=136061184;
new Uint8Array(31).fill().map(()=>x+=x>>13);в принципе даже сдвига здесь можно избежать, если он будет на четное кол-во байт, тогда память с хранимым значением можно будет с другим отступом просто замапить в альтернативную переменную (даже на JS это уже можно сделать с TypedArray, не говоря про Си)
а еще на многих машинах есть SIMD инструкции - которые позволят аж 128битами оперировать нарезая их как надо на "виртуальные разряды"
В статье Charles M. Fiduccia. 1972. Polynomial evaluation via the division algorithm the fast Fourier transform revisited. In Proceedings of the fourth annual ACM symposium on Theory of computing (STOC '72). ACM, New York, NY, USA, 88-93 рассказывается как вычислить полином степени не более N в N точках за время O(N log^3 N).
В статье самой разобраться сложно, советую смотреть Ellis Horowitz. 1974. A unified view of the complexity of evaluation and interpolation. Acta Inf. 3, 2 (June 1974), 123-133 или более поздние источники.
Вычисление значения многочлена. Все ли тривиально в этом вопросе?