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.
Yeah, I just recently learned about Estrin's method when fooling around with some polynomial approximations. I'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.
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).
> 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.
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.
If you are working over floating point, you probably with to use Estrin's method (see https://en.wikipedia.org/wiki/Estrin%27s_scheme - 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'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.
Yeah, I just recently learned about Estrin's method when fooling around with some polynomial approximations. I'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.
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).
> 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.
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.
I think multiplications are faster to do in computer land than adds? I too am curious.
Also could use analysis of dependencies to see what can happen in parallel. Or for that matter, some real benchmarks.
[dead]