Which algorithm does Python use for estimating square root value?

Viewed 177

I wonder about which algorithm does Python use for estimating square root values ? Is it Newton or Babylonian or other ?

2 Answers

In CPython, math.sqrt is implemented in terms of C/POSIX sqrt function, so the only answer to give is "whatever C/POSIX does". On systems with an assembly level square root function (e.g. x86's fsqrt) the C runtime may delegate to the chip, in which case you'd need to know the chip details to know how it performs the calculation.

There is an approximate square root and a more complicated algorithm for math.isqrt if you care to look at it. I suspect it doesn't precisely match a textbook method, given optimizations for computers won't match the way humans optimize doing math by hand.

It depends on the implementation; the language does not define the algorithm. ShadowRanger already hit two common ones. These are general, software-based methods.

However, it's quite common for the processor itself to have a machine-level SQRT function. Intel chips have implemented basic transcendental functions in the late 1980s. As a result, iPython simply in-lines the on-chip function; there is no software algorithm, as the on-chip code determines the value by a couple of hardware operations, deriving mantissa and characteristic in parallel.

Related