Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- The Lean proof is the interesting part. A 100-page construction nobody's sure about becomes something you can trust when the multiplication-count bound is machine-checked.by lee_ward
- Pretty cool, especially in finite fields. Though coefficients seem to blow up pretty quick in Q?by IsTom
- 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?
by voxelghost - 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).
by gowld - 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.by guyomes
- 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.
by emil-lp - 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.
by pvillano