Square roots with pencil and paper: the Babylonian method

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{array}{rcl} 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{array}$

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{array}{rcl} 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{array}$

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{array}{rcl} 2R & = & R + N/R \\ R & = & N/R \\ R^2 & = & N \\ R & = & \sqrt{N} \end{array}$

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.

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

10 Responses to Square roots with pencil and paper: the Babylonian method

meichenl says:

May 18, 2009 at 4:22 pm

Hi Brent,

Nice post. Just wanted to add that this method could also be considered a special case of Newton’s Method applied to the equatiion $f(x) = x^2 - n$ .
Brent says:

May 19, 2009 at 9:09 am

Hi meichenl, excellent point!
Pingback: A semana nos arXivs… « Ars Physica
Pingback: Math Teachers at Play #8 « Let’s Play Math!
Pingback: Square roots with pencil and paper: method 2 « The Math Less Traveled
Pingback: Math Teachers at Play #8 |
asmeurer says:

August 28, 2010 at 1:15 pm

Hi.

If something doubles after each iteration, it is exponential, not quadratic (compute 2^n for a few n if you don’t believe me). If the number of digits doubles after each iteration, it is actually double exponential in the number itself, because each digit is already exponentially valued (i.e., a0/10^0 + a1/10^1 + a2/10^2 + …).
- Brent says:
  
  August 31, 2010 at 4:15 pm
  
  Remember, we are talking about the number of digits after the decimal point, not the number of digits of an integer. You are right that if we had a sequence of integers where the number of digits doubled at each step, the sequence would be growing doubly exponentially. However, for the Babylonian method we are not talking about a rate of growth, but a rate of convergence. The sort of convergence exhibited by the Babylonian method is indeed called quadratic convergence, as you can read about here: http://en.wikipedia.org/wiki/Quadratic_convergence.
Pingback: Square roots with pencil and paper: method 2 | The Math Less Traveled
Pingback: Math Teachers at Play #8 « Let's Play Math!

Comments are closed.