Show HN: Compute polynomials twice as fast
A new paper proves that polynomial evaluation can be done with roughly half the multiplications of Horner's method, thanks to clever preprocessing and a rigorous Lean proof. This deep dive into computational efficiency has piqued HN's interest in its implications for cryptography, hashing, and function approximation. The accompanying interactive demo allows users to visualize the theoretical gains in practice.
The Lowdown
A recent paper co-authored by thomasahle presents a significant advancement in polynomial evaluation, demonstrating that with prior preprocessing of coefficients, the number of multiplications required can be dramatically reduced, almost by half compared to the widely used Horner's method.
- The Problem: Standard methods like Horner's require
nmultiplications for a polynomial of degreen(orn-1for monic polynomials). - The Solution: The new method, backed by a 100-page proof formalized in Lean, achieves evaluation with
⌊n/2⌋+1multiplications for monic polynomials, and one more for general ones. - Applications: This optimization has wide-ranging implications for fields relying heavily on polynomial evaluation, such as approximating functions (e.g.,
exp,sin,cos), cryptography, hashing, and coding theory. - Interactive Demo: The authors have provided a user-friendly website that allows anyone to input a polynomial, select a field, and compare various evaluation methods, including their new approach, visualizing the reduction in operations.
This work moves beyond theoretical construction, offering a practical tool and a formally verified proof for a long-standing challenge in computational mathematics, promising more efficient algorithms in various computing domains.
The Gossip
Hashing Hot Takes
The discussion heavily revolved around the applicability of this method to various hashing algorithms. Users questioned if it could speed up popular hashes like WyHash, xxh3, or Poly1305, and how it compares to CRC8. The author clarified that many 'practical' hashes don't use polynomial structures and often rely on heuristics, making them vulnerable to adversarial inputs. The core takeaway is that while the method is excellent for fixed polynomials evaluated many times (e.g., function approximation), the preprocessing cost makes it generally less suitable for universal hashes where input data defines the coefficients on the fly. However, the paper does introduce new injective polynomial hashing constructions that are more efficient.
Cycles and Computational Costs
Commenters delved into the practical implications for CPU performance, particularly the trade-offs between multiplication and addition on modern hardware. Questions arose about the role of Fused Multiply-Add (FMA) operations and the relative latency and throughput of different arithmetic operations. It was noted that while multiplications were historically slower, modern CPUs can often perform them in similar cycles to additions, and specific architectures (like AMD Zen) might have more add units than multiply units. The author pointed out that Estrin's method is often preferred for floating-point calculations due to its FMA and pipelining benefits, whereas the paper's method finds its strongest advantage in finite fields where multiplication remains significantly more expensive.
Demo Delights & Details
Many users praised the interactive demo on the website as an excellent tool for understanding the various polynomial evaluation methods. Feedback included constructive suggestions, such as improving the graph visualization by separating source nodes for powers of x. There were also bug reports concerning the 'monic' polynomial setting. A common question was why not simply use the Fast Fourier Transform (FFT) for preprocessing; the author clarified that FFT is ideal when all evaluation points are known in advance, contrasting it with scenarios like streamed inputs (e.g., polynomial hashes in hashmaps) or fixed function approximations (like Taylor series) where this new method excels.