A little while ago I wrote about the Babylonian method for approximating square roots with pencil and paper. In that post I noted that the Babylonian method is quite efficient, but annoying in some ways since it makes you deal with big fractions and/or long division. Today I’m going to describe another method for computing square roots with pencil and paper which is less efficient, but explicitly deals with the decimal representation and hence more convenient in some ways.
Here’s how it works. Let’s say we’re trying to find the square root of 7. First, we write 7 as 7.00000… and group the digits by twos, like so:
The first step is to write down the first digit of the solution. This is easy: (too small), but (too big), so we write down 2, then subtract 4 from 7 and write the remainder, and bring down the next two digits (in this example, 00).
Now, here’s the part that seems like voodoo, but don’t worry, I’ll explain why it works later! For now I’ll just stick to the how. Our answer so far is 2. We double it, getting 4, and now we look for the largest digit d for which . I'm abusing notation a bit here; by I don't mean 4 times d, I mean “the number you get by pasting the digit d after the digit 4″. Some experimenting shows that . So 6 is the digit we are looking for, and it’s the next digit in the answer. We write 6 along the top, and subtract 276 (which is 46 * 6) from 300, then bring down the next two digits:
Now we repeat the process: we first double the answer so far (26) to get 52, then we look for the largest digit d for which . Again, some experimenting shows that and , so the digit we are looking for is 4. We write 4 along the top, subtract , and bring down the next two digits:
I’ll carry it one more step: twice 264 is 528, and (whereas is too big), so we get
So far, we have computed that . And indeed, we can check that , but So, why does this work? Well, suppose we have worked out so far that
and we want to find another digit in this approximation. First, we can multiply both sides of the equality by 100:
Now we want to find the value of b so that
which will give us one more digit of precision. Expanding out the binomial on the left:
Factoring and rearranging a bit:
is the remainder; it’s what’s listed at the bottom under the most recent subtraction. The factor of 100 corresponds to bringing down the next two digits. And what do we want on the left? We want a value of b for which is less than this remainder. This looks familiar! The is where we multiply the current answer by two, and then corresponds to appending the digit b to .
So, which is better, this method or the Babylonian method? I don’t know, they are very different. I can think of situations where I would want one or the other. I guess I’ll leave the determination up to you!