Message375685
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. |
|
Date |
User |
Action |
Args |
2020-08-20 04:21:55 | tim.peters | set | recipients:
+ tim.peters, rhettinger, mark.dickinson, serhiy.storchaka |
2020-08-20 04:21:55 | tim.peters | set | messageid: <1597897315.14.0.449606933854.issue41513@roundup.psfhosted.org> |
2020-08-20 04:21:55 | tim.peters | link | issue41513 messages |
2020-08-20 04:21:54 | tim.peters | create | |
|