One book cited several times in the preprint of OP is the volume 2 of the famous book series of Knuth, The Art of Computer Programming, notably its section 4.6.4. For readers interested in this kind of results, it is a really interesting gathering of classical theorems and useful tricks to evaluate quickly polynomials.

I read your arxiv paper yesterday (or was it the day before).

Do you think this can be used to speed up the algebraic method for k-path?

If so, you should enter next years PACE challenge.

This is super cool. I learned a lot playing with the demo. I only knew Horner and Estrin, but I think I've gotten a grasp on most of them.

One small change I'd recommend is for the graph visualization, have a separate source node for each x, x^2, x^4 used. A single x source clutters the graph and hides the structure.

Pretty cool, especially in finite fields. Though coefficients seem to blow up pretty quick in Q?

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?

If you're going to preprocess the polynomial, maybe you want to evaluate it at many different points. But then why not use the FFT?

* "monic" = the leading coefficient is 1

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

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

See also discussions here https://www.reddit.com/r/programming/comments/1wbgcke/commen... on how the actual math works out.

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).

What is the tradeoff between multiplication and addition?