Fast Polynomials - Evalúa polinomios con la mitad de multiplicaciones
Show HN: Compute polynomials twice as fast
Fast Polynomials es una herramienta web que preprocesa los coeficientes de cualquier polinomio mónico para evaluarlo con solo ⌊n/2⌋+1 multiplicaciones, frente a las n del método de Horner. Solo tienes que introducir tu polinomio, elegir el campo (ℚ, ℝ, ℂ, o cuerpos finitos) y la herramienta genera una cadena de evaluación optimizada, junto con código en C y un grafo. Ideal para aproximar funciones como exp, sin o cos, y para aplicaciones en criptografía, hashing y teoría de códigos. Basado en el artículo de investigación 'Fast Evaluation of Polynomials with Rational Preprocessing' (arXiv:2609.06022, 2026), ofrece un método exacto con preprocesamiento racional, superando a técnicas clásicas como Horner, Estrin o Rabin–Winograd.
Con un poco de preprocesamiento de los coeficientes, ⌊n/2⌋+1 multiplicaciones son suficientes para cualquier polinomio mónico.
- emil-lp
Leí tu artículo de arXiv ayer (¿o fue anteayer?).
¿Crees que esto se puede usar para acelerar el método algebraico para k-path?
Si es así, deberías presentarte al desafío PACE del año que viene.
- IsTom
Muy chulo, especialmente en cuerpos finitos. Aunque los coeficientes parecen dispararse bastante rápido en Q, ¿no?
- pvillano
Esto es súper chulo. Aprendí mucho jugando con la demo. Solo conocía Horner y Estrin, pero creo que he llegado a comprender la mayoría.
Un pequeño cambio que recomendaría es que, para la visualización del grafo, tengas un nodo fuente separado para cada x, x^2, x^4 usados. Una única fuente x desordena el grafo y oculta la estructura.
- throwaway81523
Si vas a preprocesar el polinomio, quizá quieras evaluarlo en muchos puntos diferentes. Pero entonces, ¿por qué no usar la FFT?
- voxelghost
Sigue volviendo a 'monic' desde, por ejemplo, 'ln(1+x)' al cambiar entre algoritmos, y luego parece que se queda fijado en 'monic'? (¿Me estoy perdiendo algo?)
También tengo curiosidad: en tu versión frente a horner, ¿cómo se corresponden ambos algoritmos con el número de operaciones fmadd?