[issue27761] Private _nth_root function loses accuracy

[Tim Peters]

Tim Peters added the comment:

A meta-note:  one iteration of Newton's method generally, roughly speaking, doubles the number of "good bits" in the initial approximation.

For floating n'th root, it would an astonishingly bad libm pow() that didn't get more than half the leading bits in pow(x, 1/n) right.

So a single Newton iteration, if carried out in infinite precision, should be enough to get all the bits "right" (meaning not significantly worse than 0.5 ulp error when converted back to a float).

So if you find yourself doing more than one Newton iteration, you're just fighting floating-point noise.  It's an illusion - nothing is actually getting better, except perhaps by accident.

Which suggests one approach for doubles (in C - same as a Python float):  get the pow() approximation.  Feed it to a `fractions.Fraction()` constructor.  Do one Newton iteration using the Fraction type.  Then use `float()` to convert the result to a float.

I believe that's the best you can possibly do without doing real work ;-)

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue27761>
_______________________________________