Eli5: how do machines calculate the value of root of numbers that aren’t perfect squares.
In: 70
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