Show HN: Compute polynomials twice as fast
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.
Discussion Highlights (5 comments)
aetherspawn
I guess it’s not faster than using a table for CRC8?
vlovich123
Would this be applicable to fast hashes like WyHash and xxh3 or are those not using polynomials? Is this mainly for faster cryptographic hashes?
voxelghost
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?
gowld
What is the tradeoff between multiplication and addition?
gowld
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).