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 3 hours ago [-]
"monic" is a separate switch from the example functions radio-selector. Enabling "monic" removes the leading coefficient.
vlovich123 3 hours ago [-]
Would this be applicable to fast hashes like WyHash and xxh3 or are those not using polynomials? Is this mainly for faster cryptographic hashes?
orlp 51 minutes ago [-]
It is applicable to fast universal hashes like Poly1305 and Polymur (the latter of which I'm the author). However it's not clear to me whether this work improves over the state of the art for that purpose, see some questions here: https://www.reddit.com/r/programming/comments/1wbgcke/comput....
This purpose is however much easier/flexible than actual polynomial equivalence since the requirement here is only that the polynomial is injective, not identical.
WyHash and xxh3 do not have polynomial structures.
21 hours ago [-]
gowld 3 hours ago [-]
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).
aetherspawn 4 hours ago [-]
I guess it’s not faster than using a table for CRC8?
gowld 3 hours ago [-]
What is the tradeoff between multiplication and addition?
nraynaud 2 hours ago [-]
Just a few years ago, mults were slower, but I think now (Intel i9) mult, add and fma are the same.
Also I am curious, in your version vs. horner , how do both algorithms map onto number of fmadd operations?
This purpose is however much easier/flexible than actual polynomial equivalence since the requirement here is only that the polynomial is injective, not identical.
WyHash and xxh3 do not have polynomial structures.
> 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).
https://stackoverflow.com/a/39135689