Posted by thomasahle 1 day ago
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.
It takes advantage of FMA (fused multiply add), has good numeric stability and uses pipelining optimally.
A while ago I suggested using Estrin's method in Boost, for functions like std::exp. There's some interesting discussions here: https://github.com/boostorg/math/issues/924 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.
The length of an expression when written out can definitely be deceiving when pipelining is added to the mix.
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).
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.