Posts Tagged ‘pencil and paper’

Square roots with pencil and paper: method 2

Thursday, June 11th, 2009

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:

7.\;00\;00\;00\;00\dots

The first step is to write down the first digit of the solution. This is easy: 2^2 = 4 (too small), but 3^2 = 9 (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 4d \times d < 300. I'm abusing notation a bit here; by 4d 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 46 \times 6 = 276 < 300, and 47 \times 7 = 329 > 300. 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 52d \times d < 2400. Again, some experimenting shows that 524 \times 4 = 2096 and 525 \times 5 = 2625, so the digit we are looking for is 4. We write 4 along the top, subtract 524 \times 4 = 2096, and bring down the next two digits:

I’ll carry it one more step: twice 264 is 528, and 5285 \times 5 = 26425 < 30400 (whereas 5286 \times 6 is too big), so we get

So far, we have computed that \sqrt{7} \approx 2.645\dots. And indeed, we can check that 2.645^2 = 6.996\dots, but 2.646^2 = 7.001\dots So, why does this work? Well, suppose we have worked out so far that

a^2 \leq 7,

and we want to find another digit in this approximation. First, we can multiply both sides of the equality by 100:

(10a)^2 \leq 700

Now we want to find the value of b so that

(10a + b)^2 \leq 700

which will give us one more digit of precision. Expanding out the binomial on the left:

100a^2 + 20ab + b^2 \leq 700

Factoring and rearranging a bit:

(10 \times (2a) + b) b \leq 100(7 - a^2)

7 - a^2 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 (10 \times (2a) + b) b is less than this remainder. This looks familiar! The 2a is where we multiply the current answer by two, and then 10 \times (2a) + b corresponds to appending the digit b to 2a.

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!

Tags: ,
Posted in algebra, computation | 8 Comments »

Square roots with pencil and paper: the Babylonian method

Monday, May 18th, 2009

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 2^2 = 4, we see that 2 is too small. So we try 3: 3^2 = 9, 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: 2.5^2 = 6.25. 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 (3.3 \approx \log_2 10). 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:


\displaystyle R' = \frac{R + N/R}{2}.

Repeating this process will result in closer and closer approximations to \sqrt{N}.

Let’s try an example, again using N = 7 and R_0 = 2 as our initial guess. We can compute a few iterations of the process according to the above formula:

$ \begin{align*} R_1 &= (R_0 + 7/R_0)/2 = (2 + 7/2)/2 \\ &= (11/2)/2 = 11/4 \\ R_2 &= (R_1 + 7/R_1)/2 = (11/4 + 28/11)/2 \\ &= (121/44 + 112/44)/2 = 233/88 \\ R_3 &= (R_2 + 7/R_2)/2 = (233/88 + (7 \cdot 88)/233)/2 \\ &= (54289/20504 + 54208/20504)/2 \\ &= 108497/41008 \\ R_4 &= \dots = 23543191457/8898489952. \end{align*} $

How close did we get? The true value of \sqrt{7}, to 15 decimal places, is

\sqrt{7} = 2.645751311064591\dots

(Incidentally, I computed this using Wolfram|Alpha by typing “sqrt 7 to 15 digits”.) Here are our approximations, with the correct decimal places in bold:

$ \begin{align*} R_0 &= \mathbf{2} \\ R_1 &= \mathbf{2}.75 \\ R_2 &= \mathbf{2.64}77\overline{27} \\ R_3 &= \mathbf{2.64575}20483808037\dots \\ R_4 &= \mathbf{2.645751311064}6933\dots \end{align*} $

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 R = (R + N/R)/2 (that is, if R is a fixed point of this operation), then

$ \begin{align*} 2R &= R + N/R \\ R &= N/R \\ R^2 &= N \\ R &= \sqrt{N}. \end{align*} $

Also, it is not too hard to see that \sqrt{N} must lie in between R and N/R, since R \cdot N/R = N; so taking their average (which is essentially what the Babylonian method does) will necessarily give us a better approximation to \sqrt{N} 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.

Tags: , , ,
Posted in algebra, computation, convergence, iteration, number theory | 8 Comments »