Eli5: how do machines calculate the value of root of numbers that aren’t perfect squares.
In: 70
There are a bunch of methods. The one I was taught is:
(0) If your number is negative, factor out the -1, whose square root is the special number “i” and only work with the positive part.
(1). Decide how close is close enough. Maybe you need to be accurate to within 0.0001 , maybe you need to be accurate within 0.00000000001 — but there will always be a point that is close enough.
(2). Guess the square root and divide the number by it. Any reasonable guess will do — for example, the biggest integer whose square is less than your number, or even just half of your number to be simple.
(3) Divide the number by the square root guess. If the difference between the quotient and the guess is within the target accuracy, you are done.
(4) Take the average of the guess and the quotient; that’s your new guess. Go back to step 3.
This is not the most efficient algorithm, but it’s easy enough to explain to a ten year old.
(Edited: used the wrong word for quotient)
They use an algorithm. [There are a whole bunch of different algorithms for calculating roots](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots), some of which have been known for thousands of years.
Some algorithms are faster than others, depending on the machine, the numbers involved, and how accurate the answer needs to be.
The 1999 computer game Quake III Arena famously used a [weird algorithm to calculate inverse square roots](https://en.wikipedia.org/wiki/Fast_inverse_square_root), which gained a lot of attention for including the seemingly random lines
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df – ( i >> 1 ); // what the ****?
where they take away their number from 1597463007 (0x5f3759df in decimal).
This weird algorithm had been floating around the computer game and coding world since the late 80s, enough that the people at idSoftware knew of it but apparently didn’t understand it. At the time it was a much faster way of calculating inverse square roots than the standard methods (although was quickly surpassed).
The oldest method is a cheat based on knowing that the square root is going to be something in the middle between two products that make that number. This should make sense if you think about it, a little, if two numbers multiply to something, a * b = c, you can nudge a up a little and b down a little to have c stay the same. Using this, we get a method from ancient greece called Heron’s method
Lets say you want to take the root of 19.
Take a guess, lets say 6.
Divide 19/6 = 3.1667.
This tells us that the the square root is between 3.1666 and 6. So we can choose the middle between these, by taking the average (3.166 + 6)/2 = 4.583. We can choose really anything in between these numbers but the exact middle is probably gonna be the best guess.
We can repeat this process
19/4.583 = 4.145.
(4.145 + 4.583)/2 = 4.364, our next guess.
19/4.364 = 4.353
(4.364 + 4.353)/2 = 4.3585, our next guess
You can keep repeating this process until you get the desired error.
Running this even just 3 times gives us 4.3585^2 = 18.99652225, which is pretty damn close.
Newton was able to improve on this a little bit with something called Newton’s method, it actually can be used to solve for more formulas than just the square root, but its classic solution was for that of a square root.
Newton tweaks this by using a a calculus thing called a derivative to make a better guess at every iteration than taking just the average. With a better guess, the formula converges towards the square root much faster.
One method electronic computers have used to speed up calculations of roots and powers is using logarithmic lookup tables and logarithmic arithmetic to calculate powers.
If you want to calculate sqrt(x), you can do this.
sqrt(x) = x^(1/2) = e^(1/2 * ln(x))
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!
The simplest/traditional “fast” algorithm (quadratic convergence) is Newton’s method, also known as Newton-Raphson. It can be applied to many different calculations, and finding nth roots is an example where it works with hardly any theoretical work.
This is easy to explain graphically. Take square roots as an example. We want to find sqrt(n), so we set up a function f where f(x) = x^2 – n. We set up f so that it has a root at sqrt(n), essentially by definition.
Now we imagine graphing this function. We guess any random value as an initial value. A reasonable first guess would be a number with half as many bits or digits as n. We find the point on the graph of f with this x value, we draw the tangent at this point, and we find where this straight line crosses the x axis. This x value is our second guess, and we repeat.
It’s fairly easy to see qualitatively why this works if our guess is good and the function is smooth; we are basically assuming that the function is roughly a straight line, and seeing where the root would be if that were the case. Then repeat, until you are close enough for satisfactory precision. A quantitative analysis of the error and rate of convergence isn’t really ELI5, but the gist is that if the function is sufficiently smooth around the root and the initial guess, then the error in the next step is on the order of the square of the error in the current step, for any function. Note that for small errors, squaring the error means doubling the number of correct digits after the decimal place (or the number of correct bits in a computer).
I should also add that this only works on a computer because all of the steps are easy to implement. We find the derivative of f beforehand, and in this case, both f and its derivative are polynomials. Then we only need addition, subtraction, multiplication, and division to combine all of this and reproduce the above steps.
An efficient algorithm that is easy to understand is the bisection method.
Let’s start by saying the square root of 19 is between 4 and 5. 4^2 is 16, which is less than 19, and 5^2 is 25 which is greater than 19. So the answer has to be between those (since we assume and know the square root function is continuous in this range)
So our interval begins from 4 to 5. Evaluate the square root at the midpoint (4.5) and you get 20.25. That is greater than 19, which means the square root of 19 is between 4 and 4.5 (an easy way to see this is that 4^2 is 16, which is too small, and 5^2 is 25 which is too big. 4.5^2 is 20.25 and still to big, but closer than 5^2.
Halfway between 4 and 4.5 is 4.25. 4.25 is 18.0625, which is too small. So the answer is between 4.25 and 4.5. Next is 4.375, which for brevity I’ll tell you is too big. Then 4.3125 is too small. As is 4.34375.
We can keep iterating this until we have a sufficient number of decimal places. In 4 iterations, we went from knowing it was between 4 and 5 to knowing it is between 4.34375 to 4.375. We could continue this until we either run out of precision (decimal places a computer can store), or until we are satisfied with the “error” (the answer halfway between our final interval would be 4.3671875 is off by less than 0.008).
Latest Answers