Fast Polynomial Evaluation — Chain Compiler

Why it's ranked here

The claim behind it is a research result, and the repository backs it with more than prose. Any monic polynomial of degree n, over characteristic zero or a prime field larger than n, evaluates with half the degree, rounded down, plus one multiplication, which answers a question Rabin and Winograd left open. The main bound is formalized in Lean 4 with Mathlib, and a GitHub Actions job rebuilds the proofs on every push and pull request. The code is MIT licensed and the generated C is released under the no-attribution 0BSD license, so output can go straight into a product.

What's good

Every decoding claim ships with an explicit inverse rather than a numerical solver: the project's stated policy rejects sampled tests and Jacobian checks as proof of bijectivity. The Python tool verifies each decode by re-expanding the result and refuses a mismatch, and a self-test round-trips encoding and decoding up to a chosen degree. The hashing angle is concrete: drawing the chain's parameters uniformly equals drawing a uniformly random monic polynomial, which gives n-wise independence. The paper reports hashing speedups over Horner of 1.84x on an Apple M2 Pro and 2.15x on an Intel Xeon at nine-wise independence.

Tradeoffs

The schedules are exact, and the paper states that in floating point they are numerically unstable, because the rewritten constants for an arbitrary polynomial are large and cancel. That limits real-number use, the case function approximation cares about most. Additions climb to as many as 2n, against roughly n for Rabin and Winograd's scheme. Even degrees cost one multiplication more than the algebraic optimum. Characteristic two, the setting of binary-field hashing, has fixed constructions only for odd degrees up to 25, Lean checks cover degrees 5 to 16, and a uniform construction is listed as open. The Python reference does not handle characteristic two.

How to use it well

Best fit: hashing or coding-theory code over prime fields or binary fields, where arithmetic is exact and multiplications dominate the cost. Compile the polynomial, download the C benchmark bundle and run it on the target machine, since the project warns that timings depend on architecture and compiler. Hardware binary-field kernels need x86-64 with PCLMULQDQ or ARM64 with PMULL. For approximating functions in double precision, stay with Horner or Estrin unless you have measured the error on your inputs. Researchers can script the compiler from Python or recheck the proofs with one Lake build.

Observed

License

MIT for the repository; generated C under 0BSD

Interfaces

Browser compiler with no build step, Python command-line tools, Lean 4 library

Formal proofs

Lean 4 formalization built with Lake on Mathlib

Multiplication bound

floor(n/2)+1 multiplications for monic degree n, characteristic zero or above n

Numerical stability

Unstable in floating point; intended for exact or modular arithmetic

Hardware targets

Binary-field C kernels for x86-64 PCLMULQDQ or AArch64 PMULL

Python reference fields

Odd prime fields and exact rationals; characteristic 2 not supported

Continuous integration

GitHub Actions runs the Lean build on push and pull request