Comment by thomasahle
4 hours ago
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.