Everyone knows how to add, subtract, multiply and divide with pencil and paper; but do you know how to find square roots without a calculator? (Incidentally, I highly recommend reading The Feeling of Power by Isaac Asimov, a short story about a future in which humans are so reliant on computers that they have forgotten how to do arithmetic.)
An obvious method is to guess and check while keeping track of lower and upper bounds. For example, if we wanted to find the square root if 7, we might start by guessing that the square root is 2. Computing , we see that 2 is too small. So we try 3: , so 3 is too big! So we know the square root of 7 must be somewhere in between 2 and 3. Let’s try 2.5: . So 2.5 is too small, and the square root of 7 is somewhere between 2.5 and 3. We might try 2.7 next (too big), and so on.
This works, but it is extremely tedious and inefficient! We can cut the search range in half at each step, but this means that on average we only add a single new decimal place every 3.3 steps or so (). Not to mention that at each step we have to compute the square of increasingly long numbers. There are at least two better methods; I’ll share one of them today and one in a future post.
The first method is often called the “Babylonian method” since it was known to the ancient Babylonians. Here’s how it works. Say we are trying to find the square root of N. Just like with the guess and check method, we start out with some guess R. Then we compute a new value for R as follows:
Repeating this process will result in closer and closer approximations to .
Let’s try an example, again using and as our initial guess. We can compute a few iterations of the process according to the above formula:
How close did we get? The true value of , to 15 decimal places, is
Wow! That converges pretty fast. In fact, this method converges quadratically—the number of correct decimal places approximately doubles with every step!
So, why does this work? Well, first of all, note that if (that is, if R is a fixed point of this operation), then
Also, it is not too hard to see that must lie in between and , since ; so taking their average (which is essentially what the Babylonian method does) will necessarily give us a better approximation to at each step.
The Babylonian method is one of the fastest-converging methods for computing square roots, but it can be somewhat inconvenient. You have to choose whether to do all the calculations with fractions and then convert to a decimal representation at the end (as I did above), which means you have to deal with multiplying rather large numbers; or use a decimal representation throughout, which means you have to do some annoying long division. There’s another method which doesn’t converge as quickly but can be much more convenient, since it explicitly uses decimal notation and involves somewhat more manageable operations; I’ll describe this other method in an upcoming post.
For more reading on the Babylonian method and a number of related generalizations, check out this MathPages article.