Fast Polynomial Evaluation - Compute polynomials twice as fast
Fast Polynomial Evaluation — это интерактивный компилятор цепочек вычислений, который позволяет оценивать многочлены почти вдвое быстрее, чем классический метод Горнера. С помощью предварительной обработки коэффициентов он сокращает количество умножений до ⌊n/2⌋+1 для унитарных многочленов. Просто введите многочлен, выберите поле (рациональные, вещественные, комплексные или конечные поля) и получите оптимизированную цепочку в математической записи, коде на C или в виде графа. Инструмент основан на новой научной работе (arXiv:2609.06022) и поддерживает сравнение с методами Хорнера, Эстрина, Рабина–Винограда, Кнута–Ива и Пана. Это полезно для аппроксимации функций, криптографии, хеширования и теории кодирования.
С помощью небольшой предварительной обработки коэффициентов достаточно ⌊n/2⌋+1 умножений для любого унитарного многочлена — и это в два раза быстрее, чем вы могли себе представить!
- pvillano
Это очень круто. Я многое узнал, играясь с демо. Я знал только Horner и Estrin, но, кажется, я разобрался с большинством из них.
Одно небольшое изменение, которое я бы рекомендовал, — для визуализации графа сделать отдельный исходный узел для каждого x, x^2, x^4. Единый источник x загромождает граф и скрывает структуру.
- throwaway81523
Если вы собираетесь предварительно обрабатывать многочлен, возможно, вы захотите вычислить его во многих различных точках. Но тогда почему бы не использовать FFT?
- thomasahle
См. также обсуждения здесь https://www.reddit.com/r/programming/comments/1wbgcke/commen... о том, как на самом деле работает математика.