What does the fast-polynomial paper claim?

Ahle and Knudsen (arXiv:2609.06022, 2026) show any monic degree-n polynomial can be evaluated with ⌊n/2⌋+1 multiplications after exact rational preprocessing of the coefficients, resolving the multiplication side of the 1972 Rabin–Winograd conjecture. Preprocessing is one-time and per-polynomial.

Is it faster than Horner's rule in practice?

Not in a naive interpreter. My Python benchmark over GF(2^61-1) found the compiled chain ran 0.17x the speed of Horner despite using half the multiplications, because interpreter overhead dominates. The win appears in C with carry-less multiplication kernels, where gate count maps to hardware cost, and in O(log n) multiplicative depth for parallel evaluation.

Does the reference compiler support all polynomial degrees?

No. In my sweep of monic degrees 1-64 over GF(2^61-1), 24 degrees raised NotImplementedError — every degree ≡ 3 mod 4 from 19 upward and every multiple of 4 from 20 upward. The theorem covers them (with a Lean 4 proof), but the coefficient decoders for those splittable families are not yet implemented in the reference Python compiler.

Who is fast polynomial evaluation useful for?

Anyone evaluating the same polynomial many times: universal and k-wise independent polynomial hashing (Polymur, Poly1305-style MACs), Shamir secret sharing, error-correcting codes, and function approximation in hardware, where fewer multiplications and lower multiplicative depth directly cut cost and latency.

Fast Polynomial Evaluation: Half of Horner's Multiplications

Yesterday a Show HN hit the front page claiming you can evaluate any polynomial with half the multiplications of Horner's rule. That's a 54-year-old conjecture — Rabin and Winograd, 1972 — and the repo claims it's now a theorem with a working compiler. I cloned it, ran it over every degree from 1 to 64, and got a result the README doesn't advertise: the theory holds, the reference implementation doesn't. 40 of 64 degrees compile. Here's what I measured.

What the Paper Claims

Horner's rule evaluates a monic degree-n polynomial in n-1 multiplications. The paper — Fast Evaluation of Polynomials with Rational Preprocessing by Thomas D. Ahle and Jakob B. T. Knudsen (arXiv:2609.06022, published September 5, 2026) — shows that with preprocessing of the coefficients (exact rational arithmetic: divisions and a small triangular solve, no root finding), ⌊n/2⌋+1 multiplications suffice. That closes the multiplication side of the 1972 Rabin–Winograd conjecture, which had n/2 + 2⌈log₂n⌉ multiplications and assumed the log overhead was necessary. It wasn't.

The catch, and it's a real one: preprocessing is per-polynomial and one-time. This is not a drop-in Horner replacement. It's for the case where you evaluate the same polynomial many times — polynomial hashing, MACs, error-correcting codes, function approximation.

Running the Compiler

The repo (thomasahle/fast-polynomials) is 7,000+ lines of Python reference compiler, a Lean 4 formalization of the theorem, and a browser compiler that emits C. I compiled the probabilists' Hermite polynomial He₇ = x⁷ − 21x⁵ + 105x³ − 105x:

# Horner: 6 multiplications. Compiler:
python3 tools/poly_schedule.py --check 1 -21 0 105 0 -105 0 1

# muls: 4 (target 4 for monic degree 7)
y0 = (x) * (x - 137872)
y1 = (x + y0 + 19008412588) * (x + 137871)
y2 = (y1 - 2620708851920149) * (x)
y3 = (x + y1 - 2620708851920148) * (y2 - 2651)
out = y0 + y2 + y3 + 1
# --check: OK

Four multiplications instead of six, verified exact by the built-in checker at random points. The five large constants come from the coefficients through an explicit decoder — they're exact rationals, and the same chain shape works over ℚ, over Mersenne prime fields, and over carry-less GF(2^n) fields that polynomial hashing uses.

My Benchmark: 40 of 64 Degrees Compile

I swept every monic degree 1 through 64 with random coefficients over GF(2⁶¹−1), compiled each, counted multiplication gates, and checked the result against Horner at 4 random field points per degree.

# /opt/data/dk_bench.py — survey + correctness + wall-clock
chain = compile_polynomial_chain(coeffs, modulus=(1 << 61) - 1)
assert len(chain.gates) <= n // 2 + 1

Results:

Multiplication bound: holds. All 40 compilable degrees came in at or below ⌊n/2⌋+1 gates. Zero overages.
Correctness: holds. All 40 degrees × 4 points matched Horner exactly over GF(2⁶¹−1), and the rational decoder matched exact-Fraction Horner on all 23 of 31 degrees it ran over ℚ.
Coverage: the gap. 24 of 64 degrees raise NotImplementedError: every degree ≡ 3 mod 4 from 19 up (19, 23, 27, 31, …), and every multiple of 4 from 20 up, because even-degree compilation peels off x·P₍ₙ₋₁₎ and needs the odd degree below it. The paper proves these cases; the reference decoder just hasn't implemented the "splittable-family" decoders for them yet — the peeling fallback is intentionally disabled in the source.

The Wall-Clock Trap

The HN comments asked the obvious question: is it actually faster? In Python, no — and that's informative:

=== wall-clock, Python, GF(2^61-1), 200k evals ===
deg 21: Horner 20 muls  0.95s | chain 11 muls  5.93s | 0.16x
deg 41: Horner 40 muls  1.92s | chain 21 muls 10.68s | 0.18x
deg 61: Horner 60 muls  2.85s | chain 31 muls 16.32s | 0.17x

Six times slower with half the multiplications. The interpreted chain evaluator (dataclass gates, dict lookups) swamps any mult savings. The paper's own benchmarks don't run Python — they benchmark C with PCLMULQDQ/PMULL carry-less kernels over GF(2⁶⁴) for hashing, where the gate count is what the hardware bills you for. The other real prize is depth: these chains have multiplicative depth O(log n) versus Horner's serial n, which matters for parallel hardware and MPC. If you want the speedup today, use the website's C emitter, not the Python reference.

Bottom Line

This is genuine theory news: a 1972 conjecture closed, with code, a Lean proof, and a browser compiler. The multiplication-count theorem survived everything I threw at it. But the reference implementation covers 63% of the degree range up to 64, and the headline is about multiplication count, not wall-clock — in a naive Python interpreter the "faster" chain loses 6x. Treat this as a compiler for hardware and hashing stacks, not a libc-level Horner swap. And treat "resolved a 54-year conjecture, shipped with a working compiler" as the new bar for math-on-GitHub: this is what open-weights-era theory repos look like.

What the Paper Claims

Running the Compiler

My Benchmark: 40 of 64 Degrees Compile

The Wall-Clock Trap

Bottom Line

Related