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.

It&#x27;s the blessing and the course of a polynomial inverse: the inverse is the same degree as the polynomial, so its largest coeffecient is large and blows up. 
Knuth-Eve and Pan use the root of a degree d polynomial, which is slightly less big, but still inpractical.

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

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&gt; have a separate source node for each x, x^2, x^4 usedDo you mean a graph like this R&amp;W? <a href="https:&#x2F;&#x2F;thomasahle.com&#x2F;fast-polynomials&#x2F;#ex=bessel&amp;mode=Q&amp;method=Rabin%E2%80%93Winograd&amp;view=graph&amp;form=original&amp;cstyle=float&amp;numfmt=exact&amp;deg=9" rel="nofollow">https:&#x2F;&#x2F;thomasahle.com&#x2F;fast-polynomials&#x2F;#ex=bessel&amp;mode=Q&amp;me...</a>
there are nodes labeled x2, x4, x8; but it&#x27;s the output of multiplications, and we want to make the number of mults visually clear.

This is super cool. I learned a lot playing with the demo. I only knew Horner and Estrin, but I think I&#x27;ve gotten a grasp on most of them.One small change I&#x27;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.

FFT multipoint evaluation is great when you know all the evaluation points in advance. However, for many practical applications the input is only streamed to you. E.g. a polynomial hash for a hashmap. Or preprocessing the taylor approximation of exp(x) for a standard library.

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

&quot;monic&quot; is a separate switch from the example functions radio-selector. Enabling &quot;monic&quot; removes the leading coefficient.

It keeps flipping back to &#x27;monic&#x27; from e.g. &#x27;ln(1+x)&#x27; when switching between algorithms, and then seems to lock to &#x27;monic&#x27;? (Am I missing something?)Also I am curious, in your version vs. horner , how do both algorithms map onto number of fmadd operations?

WyHash and xxh3 are not polynomial, in fact this is one of the issues we try to solve in the paper.Many &quot;practical&quot; hashes use heuristics instead of real field multiplications to be faster. But it means they are vulnerable to adversarial inputs. That means, it&#x27;s possible to design a set of keys that have much higher probability (under random hash seeds&#x2F;keys) to collide than you&#x27;d expect under a correct hash function.We actually analyze both WyHash and xxh3 in this setting in section &quot;Adversarial inputs for heuristic hashes&quot; - <a href="https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;2609.06022#page=165" rel="nofollow">https:&#x2F;&#x2F;arxiv.org&#x2F;pdf&#x2F;2609.06022#page=165</a>

It is applicable, but it is not useful.Universal hashes use the input text as the set of coefficients.This method requires additional preprocessing of the coefficients, before starting to evaluate the polynomial. That preprocessing would slow the hashing algorithm more than what is gained during evaluation.This method is useful only when with a given polynomial, i.e. set of polynomial coefficients, you want to evaluate that polynomial many times, so the cost of the preprocessing is amortized.However, this application is very important because most functions are approximated either with polynomials or with rational functions, so this method can accelerate the evaluation of all such approximated functions.

It is applicable to fast universal hashes like Poly1305 and Polymur (the latter of which I&#x27;m the author). However it&#x27;s not clear to me whether this work improves over the state of the art for that purpose, see some questions here: <a href="https:&#x2F;&#x2F;www.reddit.com&#x2F;r&#x2F;programming&#x2F;comments&#x2F;1wbgcke&#x2F;compute_polynomials_twice_as_fast&#x2F;p8ru4k6&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.reddit.com&#x2F;r&#x2F;programming&#x2F;comments&#x2F;1wbgcke&#x2F;comput...</a>.This purpose is however much easier&#x2F;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.

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

See also discussions here <a href="https:&#x2F;&#x2F;www.reddit.com&#x2F;r&#x2F;programming&#x2F;comments&#x2F;1wbgcke&#x2F;comment&#x2F;p8qhrhs&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.reddit.com&#x2F;r&#x2F;programming&#x2F;comments&#x2F;1wbgcke&#x2F;commen...</a> on how the actual math works out.

In CRC8 you interpret the input as coefficients of a polynomial, and take mod `x⁸ + x² + x + 1`.
The problem we solve here is a bit different: You know the coefficients in advance, and want to preprocess the polynomial to make it fast to evaluate.However, in section &quot;5.9 Injective Polynomial Hashing&quot; we actually study the problem of universal hashing, which is a lot more like CRC8.

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

I don&#x27;t know what happened to the URL, but it&#x27;s supposed to link to this paper: <a href="https:&#x2F;&#x2F;www.gwizfl.org&#x2F;email&#x2F;cr.yp.to&#x2F;antiforgery&#x2F;pema-20071022.pdf" rel="nofollow">https:&#x2F;&#x2F;www.gwizfl.org&#x2F;email&#x2F;cr.yp.to&#x2F;antiforgery&#x2F;pema-20071...</a>It&#x27;s a very nice construction (based on Rabin &amp; Winograd&#x27;s polynomial multiplication method) for building universal hashes with n&#x2F;2+O(logn) multiplications.The annoying part is that it&#x27;s a tree structure, which is not usually what you want in a fast hash that you&#x27;re folding over a data stream. Some papers like <a href="https:&#x2F;&#x2F;eprint.iacr.org&#x2F;2017&#x2F;328.pdf" rel="nofollow">https:&#x2F;&#x2F;eprint.iacr.org&#x2F;2017&#x2F;328.pdf</a> try to fix this, but there are a lot of annoying trade-offs.A famous fast hash is NH, which is just:<pre><code> H(x) = sum_i (x_{2i} + a_{2i}) * (x_{2i+1} + a_{2i+1})
</code></pre>
where `a_i` are random keys. No modulus needed. The issue is that you need as many random keys as the length of the input.Our construction (section 5.9 Injective Polynomial Hashing) shows that you can do something a bit similar with polynomials:<pre><code> P_0 = z
 P_i = x_{2i} + (x_{2i+1} + z^3)(x_{2i} + z^2)
</code></pre>
this is a lot simpler than Bernstein&#x27;s, and is still n&#x2F;2 multiplications.

From the abstract, a name that many on HN would recognize:&gt; 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).

Yeah, I just recently learned about Estrin&#x27;s method when fooling around with some polynomial approximations. I&#x27;d been scaling the output by a sqrt term to get better accuracy at small degrees, but it turned out that polynomials of very large degrees can be calculated in the same time as a single correctly-rounded sqrt, especially when fma is available. Seemingly, the only real cost is the added register pressure.The length of an expression when written out can definitely be deceiving when pipelining is added to the mix.

If you are working over floating point, you probably with to use Estrin&#x27;s method (see <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Estrin%27s_scheme" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Estrin%27s_scheme</a> - also tab 3 on the website.)It takes advantage of FMA (fused multiply add), has good numeric stability and uses pipelining optimally.A while ago I suggested using Estrin&#x27;s method in Boost, for functions like std::exp. There&#x27;s some interesting discussions here: <a href="https:&#x2F;&#x2F;github.com&#x2F;boostorg&#x2F;math&#x2F;issues&#x2F;924" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;boostorg&#x2F;math&#x2F;issues&#x2F;924</a> if you are interested in all the practical details.However, for finite fields (e.g. used for hashing and cryptography) multiplication is much more expensive than addition, which is the main use of this algorithm.

&gt; Many CPUs, like the AMD Zen CPUs, have more execution units that can do additions, than those that can do multiplicationsAnd the reasons for that it takes way more transistors to implement a fast rabbit^W multiplier than to implement a fast adder, so adding an execution unit that cannot multiply is easier to warrant than adding one that can.

In modern computers, the throughput of an execution unit is the same for multiplications and additions, but multiplication frequently has a greater latency, by 1 or 2 clock cycles.Many CPUs, like the AMD Zen CPUs, have more execution units that can do additions, than those that can do multiplications. So the aggregated throughput over all execution units can be higher for additions than for multiplications.For example, for floating-point numbers, the AMD Zen CPUs have 4 vector execution units, where all 4 can do additions, but only 2 of them can do multiplications or fused multiply-add operations. So Zen CPUs can do up to 4 additions + 2 multiplications per clock cycle (when 2 multiplication-addition pairs are fused).

The answer&#x27;s all over the place with each successive CPU generation. Originally Intel CPUs had adds faster than multiplies, then both went through the FMA unit so they were the same, then they added a fast FP adder, etc. And current timings on uops.info now show FP fma 4c and mul 3c over two multiply units, and add 2c over two separate addition units.

Just a few years ago, mults were slower, but I think now (Intel i9) mult, add and fma are the same.<a href="https:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;39135689" rel="nofollow">https:&#x2F;&#x2F;stackoverflow.com&#x2F;a&#x2F;39135689</a>

Also could use analysis of dependencies to see what can happen in parallel. Or for that matter, some real benchmarks.

I think multiplications are faster to do in computer land than adds? I too am curious.

What is the tradeoff between multiplication and addition?

Show HN: Compute polynomials twice as fast