Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Show HN: Compute polynomials twice as fast

thomasahle.com

Post reply on HN
Print view View original

21–30 of 41 posts

Re: Show HN: Compute polynomials twice as fast

#21

Post by adrian_b »

gowld wrote: post #6

What is the tradeoff between multiplication and addition?

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

Re: Show HN: Compute polynomials twice as fast

#22

Post by thomasahle »

aetherspawn wrote: post #3

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

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 "5.9 Injective Polynomial Hashing" we actually study the problem of universal hashing, which is a lot more like CRC8.

Re: Show HN: Compute polynomials twice as fast

#23

Post by pvillano »

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.

Re: Show HN: Compute polynomials twice as fast

#24

Post by thomasahle »

throwaway81523 wrote: post #18

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?

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.

Re: Show HN: Compute polynomials twice as fast

#25

Post by thomasahle »

pvillano wrote: post #23

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.

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 visually clear.

Re: Show HN: Compute polynomials twice as fast

#27

Post by ack_complete »

nraynaud wrote: post #11
gowld wrote: post #6

What is the tradeoff between multiplication and addition?

Just a few years ago, mults were slower, but I think now (Intel i9) mult, add and fma are the same. https://stackoverflow.com/a/39135689

The answer'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.

Re: Show HN: Compute polynomials twice as fast

#28

Post by thomasahle »

adrian_b wrote: post #16
orlp wrote: post #12

Earlier quoted context omitted.

It is applicable to fast universal hashes like Poly1305 and Polymur (the latter of which I'm the author). However it's not clear to me whether this work improves over the state of the art for that purpose, see some questions here: https://www.reddit.com/r/programming/comments/1wbgcke/comput... . This purpose is however much easier/flexible than actual polynomial equivalence since the requirement here is only that the…

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 eva…

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

There is no preprocessing at hash time in either use.

Universal hashing: the message words are the parameters of the chain, a_i and b_i in P_i = a_i + (b_i + y)(P_{i−1} + u), not coefficients of a target polynomial. Distinct messages give distinct polynomials, which is all a universal hash needs; the decoder never runs. Same as Bernstein's BRW.

k-independent hashing: the key should be a uniformly random monic polynomial of degree k. Our parameterisation is a bijection onto those polynomials, with the rational preprocessing as its inverse, so uniformly random gate constants give a uniformly random polynomial. You draw the ⌊k/2⌋+1 constants and evaluate; the coefficients are never computed. That is why the paper needs bijective rather than just injective constructions, and the Section 5 speedups are for the whole hash.

Preprocessing only appears when a fixed polynomial (a Taylor approximation, a secret-sharing polynomial) is evaluated at many points, and then it runs once.

Re: Show HN: Compute polynomials twice as fast

#29

Post by adrian_b »

thomasahle wrote: post #28
adrian_b wrote: post #16

Earlier quoted context omitted.

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 eva…

> 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. There is no preprocessing at hash time in either use. Universal hashing: the message words are the parameters of the chain, a_i and b_i in P_i = a_i + (b_i + y)(P_{i−1} + u), not coefficients of a target polynom…

There are many kinds of universal hashing, many of which are not based on polynomial evaluation.

However, the most common kinds of universal hashing, i.e. those which are used for computing message authentication codes (MAC) in the TLS and SSH protocols (using poly1305 or GCM), are based on polynomial evaluation, where the message is the sequence of coefficients of the polynomial and the secret key of the MAC is the value at which the polynomial is evaluated.

The polynomial corresponding to a MAC is evaluated only once at the sender and once at the receiver, usually in a single pass over the data, simultaneously with its encryption or decryption. Frequently the reading or writing of the data from/to the main memory limits the throughput of the MAC computation (caches do not help, because the data is not reused), in which case a better algorithm than Horner cannot provide significant speed-ups.

Besides their application in MACs, which is ubiquitous now in Internet communication, I consider the other applications of universal hashing as minor, because the "universality" property of such hashes seldom provides any substantial benefit over alternative hash functions that do not have this property, but which guarantee other more useful properties. (The "universality" property is just a statistical property of a family of hash functions, while instantiated universal hashes may happen to be quite bad hash functions. For instance, in AES-GCM it is possible to choose by bad luck a secret key for which some reordered messages have the same hash value with the original message, so tampering with the message remains undetected. Fortunately, the adversary cannot guess when the sender has chosen a bad secret key, in order to try to alter the message.)

Re: Show HN: Compute polynomials twice as fast

#30

Post by Someone »

adrian_b wrote: post #21
gowld wrote: post #6

What is the tradeoff between multiplication and addition?

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 exam…

> Many CPUs, like the AMD Zen CPUs, have more execution units that can do additions, than those that can do multiplications

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

Post reply on HN