Show HN: Compute polynomials twice as fast

#1

Post by thomasahle » Wed, Sep 09, 2026, 8:53 AM UTC

A few years ago my coauthor and I was wondering if we could reduce the number of multiplications used for hashing algorithms. We had a construction and a 100 page proof, but we were not 100% sure it was correct. Now we have a full Lean proof, so we decided to publish it.

I made this website to make it easy for anyone how has polynomials to evaluate to see how it would be done using our method, as well as a number of previous approaches by Knuth and others.

Show HN: Compute polynomials twice as fast
thomasahle.com

Re: Show HN: Compute polynomials twice as fast

#2

Post by [deleted] » Wed, Sep 09, 2026, 9:18 AM UTC

[deleted]

Re: Show HN: Compute polynomials twice as fast

#3

Post by aetherspawn » Thu, Sep 10, 2026, 2:18 AM UTC

I guess it’s not faster than using a table for CRC8?

Re: Show HN: Compute polynomials twice as fast

#4

Post by vlovich123 » Thu, Sep 10, 2026, 2:30 AM UTC

Would this be applicable to fast hashes like WyHash and xxh3 or are those not using polynomials? Is this mainly for faster cryptographic hashes?

Re: Show HN: Compute polynomials twice as fast

#5

Post by voxelghost » Thu, Sep 10, 2026, 2:30 AM UTC

It keeps flipping back to 'monic' from e.g. 'ln(1+x)' when switching between algorithms, and then seems to lock to 'monic'? (Am I missing something?)

Also I am curious, in your version vs. horner , how do both algorithms map onto number of fmadd operations?

Re: Show HN: Compute polynomials twice as fast

#6

Post by gowld » Thu, Sep 10, 2026, 2:33 AM UTC

What is the tradeoff between multiplication and addition?

Re: Show HN: Compute polynomials twice as fast

#7

Post by gowld » Thu, Sep 10, 2026, 2:37 AM UTC

From the abstract, a name that many on HN would recognize:

> We also give an injective polynomial construction for universal hashing that uses N multiplications to hash 2N values with a single random key. This improves the best previous construction by Daniel J. Bernstein (this http URL).

Re: Show HN: Compute polynomials twice as fast

#8

Post by gowld » Thu, Sep 10, 2026, 2:41 AM UTC

voxelghost wrote: post #5

It keeps flipping back to 'monic' from e.g. 'ln(1+x)' when switching between algorithms, and then seems to lock to 'monic'? (Am I missing something?) Also I am curious, in your version vs. horner , how do both algorithms map onto number of fmadd operations?

"monic" is a separate switch from the example functions radio-selector. Enabling "monic" removes the leading coefficient.

Re: Show HN: Compute polynomials twice as fast

#9

Post by gigatexal » Thu, Sep 10, 2026, 2:54 AM UTC

gowld wrote: post #6

What is the tradeoff between multiplication and addition?

I think multiplications are faster to do in computer land than adds? I too am curious.

Re: Show HN: Compute polynomials twice as fast

#10

Post by hyperhello » Thu, Sep 10, 2026, 3:06 AM UTC

gigatexal wrote: post #9

gowld wrote: post #6

What is the tradeoff between multiplication and addition?

I think multiplications are faster to do in computer land than adds? I too am curious.

Also could use analysis of dependencies to see what can happen in parallel. Or for that matter, some real benchmarks.