Eli5: how do machines calculate the value of root of numbers that aren’t perfect squares.
In: 70
As everyone keeps mentioning it but nobody actually spelled it out, here’s Newton’s method to calculate √a:
Start with any reasonable guess for √a, be it 1, a, or whatever. Call that starting guess c.
Now calculate a better guess (c + a/c) / 2. Why this one? The two numbers c and a/c multiply to a, so one is too large, the other too low. So their average is much closer to √a.
Hence we got a new, better guess, d = (c + a/c) / 2. We then use it again, calculating (d + a/d) / 2, arriving at an even better estimate. And so on and on.
For example, calculating √7 with the starting guess c=2 gives us the following increasingly good approximations:
– 2, with 2^2 = 4
– (2 + 7/2) / 2 = 11/4 = 2.75, with 2.75^2 = 7.5625
– (11/4 + 7/(11/4)) / 2 = 2.64772…, with 2.64772…^2 = 7.0104…
– 2.64575204838…, with square 7.0000039…
– 2.64575131106…, with square 7.0000000000…
It took us only 4 steps to get an accuracy of ~10 digits. It can be shown that the correct digits at least double every time, so if we want another 10, we only have to do one more step!
Latest Answers