Fast Polynomial Evaluation - Compute polynomials twice as fast
Fast Polynomial Evaluation — это интерактивный компилятор цепочек вычислений, который позволяет оценивать многочлены почти вдвое быстрее, чем классический метод Горнера. С помощью предварительной обработки коэффициентов он сокращает количество умножений до ⌊n/2⌋+1 для унитарных многочленов. Просто введите многочлен, выберите поле (рациональные, вещественные, комплексные или конечные поля) и получите оптимизированную цепочку в математической записи, коде на C или в виде графа. Инструмент основан на новой научной работе (arXiv:2609.06022) и поддерживает сравнение с методами Хорнера, Эстрина, Рабина–Винограда, Кнута–Ива и Пана. Это полезно для аппроксимации функций, криптографии, хеширования и теории кодирования.
С помощью небольшой предварительной обработки коэффициентов достаточно ⌊n/2⌋+1 умножений для любого унитарного многочлена — и это в два раза быстрее, чем вы могли себе представить!
- emil-lp
Я читал вашу статью на arxiv вчера (или это было позавчера).
Как вы думаете, можно ли это использовать для ускорения алгебраического метода для k-path?
Если да, вам стоит поучаствовать в PACE challenge в следующем году.
- IsTom
Довольно круто, особенно в конечных полях. Хотя коэффициенты, кажется, довольно быстро раздуваются в Q?
- pvillano
Это супер круто. Я много узнал, играя с демо. Я знал только Horner и Estrin, но, думаю, я разобрался с большинством из них.
Одно небольшое изменение, которое я бы рекомендовал для визуализации графа: сделайте отдельный исходный узел для каждого используемого x, x^2, x^4. Единый источник x загромождает граф и скрывает структуру.
- throwaway81523
Если вы собираетесь предварительно обрабатывать полином, возможно, вы захотите вычислять его во многих различных точках. Но тогда почему бы не использовать FFT?
- voxelghost
Он продолжает переключаться обратно на 'monic' с, например, 'ln(1+x)' при переключении между алгоритмами, а затем, кажется, застревает на 'monic'? (Я что-то упускаю?)
Также мне интересно, в вашей версии по сравнению с horner, как оба алгоритма отображаются на количество операций fmadd?