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.
- pvillano
Esto es súper genial. Aprendí un montón 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, haya un nodo fuente separado para cada x, x^2, x^4 utilizados. Una única fuente x desordena el grafo y oculta la estructura.
- throwaway81523
Si vas a preprocesar el polinomio, quizás 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?