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.
Show HN: Compute polynomials twice as fast
41–43 of 43 posts
Re: Show HN: Compute polynomials twice as fast
#42Earlier quoted context omitted.
No, though even a hash like xxh3 can be useful when speed is more important than collision resistance. There are many hashes that use more thorough mixing functions than can be achieved with one or a few arithmetic operations (like in universal hashes), thus for them the collision probability reaches the limit imposed by the length of the hash value. Modern CPUs have various instructions that can be exploited in mixi…
It's true that you can use AES instructions now on some computers, bit I honestly don't see why you'd use a heuristic hash (even if cryptographic) when you can get provable guarantees with k-wise independent hashing. Our paper makes these even faster than they already were. See section 5.7 and 5.8 in the paper for experiments against other hashes.
You benchmarked a really old heuristic hash in Murmur and xxh64. xxh3 is ~1.6x to 1.8x faster than xxh64 - extrapolating that to 5.7 in your paper puts it at ~18-27% faster. WyHash and UMash sometimes report faster numbers.
Even xxh3 isn't the cutting edge - gxhash (~1.8x faster) and aesni (~1.5x faster) use AES instructions. Compared to your approach that perf disparity should grow to ~30-40%.
Hopefully that answers your question about why someone might still choose to use heuristic hashing rather than k-wise independent hashing when collision resistance isn't critical.
Re: Show HN: Compute polynomials twice as fast
#43This 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.
Thank you! It was a lot of fun to make the website and see all the methods in practice after having just looked at the theory for a long time :D > have a separate source node for each x, x^2, x^4 used Do you mean a graph like this R&W? https://thomasahle.com/fast-polynomials/#ex=bessel&mode=Q&me... there are nodes labeled x2, x4, x8; but it's the output of multiplications, and we want to make the number of mults visu…
I forgot that the purpose of your site is comparing the number of mults. A more compatible idea is to rearrange the nodes so that any repeated squaring is always in a single row at the top. The graph would have the same nodes and connectivity, but a more structured flow. If I ever make my own comparison of polynomial evaluation strategies I'll do manual layout.
For completeness: To apply my original idea to R&W9 you would have 5 nodes labeled x, each with one arrow out, two nodes labeled x^2, each with no arrows in and one arrow out, one node labeled x^4 with no arrows in and one arrow out, one node labeled x^8 with no arrows in and one arrow out. Three missing mults, but way fewer crossings, not what you want.