[issue41513] Scale by power of two in math.hypot()

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

Just FYI, if the "differential correction" step seems obscure to anyone, here's some insight, following a chain of mathematical equivalent respellings:

result + x / (2 * result) =
result + (sumsq - result**2) / (2 * result) =
result + (sumsq - result**2) / result / 2 =
result + (sumsq / result - result**2 / result) / 2 =
result + (sumsq / result - result) / 2 =
result + sumsq / result / 2 - result / 2 =
result / 2 + sumsq / result / 2 =
(result + sumsq / result) / 2

I hope the last line is an "aha!" for you then:  it's one iteration of Newton's square root method, for improving a guess "result" for the square root of "sumsq". Which shouldn't be too surprising, since Newton's method is also derived from a first-order Taylor expansion around 0.

Note an implication: the quality of the initial square root is pretty much irrelevant, since a Newton iteration basically doubles the number of "good bits".  Pretty much the whole trick relies on computing "sumsq - result**2" to greater than basic machine precision.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue41513>
_______________________________________