Show HN: Compute Polynomials Twice as Fast
Evaluate a degree-n polynomial with about n/2 multiplications. Type a polynomial, pick ℚ, ℝ, ℂ, a Mersenne prime or a binary field, and get the preprocessed evaluation chain as math, C code or a circuit — everything runs in your browser.
Summary not yet generated for this article.
Original Text
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.
Comments (42 of ) ⌛