Babylonian (Divide-and-Average) Algorithm for Square Roots

Even though the ancient Babylonians did not have calculators, they could still compute square roots by hand with a high degree of accuracy using a recursive process often known as the divide-and-average algorithm. When you iterate the procedure several times, you obtain a fraction (rational number) that closely approximates the true square root of a number.

Because the Babylonian method involves division with very large numbers, it fell out of favor for practical usage after the long division method for calculating square roots was discovered. Nevertheless, it is an efficient algorithm still used in many scientific and mathematical applications.

Step 1: Call the number whose square root you wish to calculate N and your initial guess A0. You can pick any number for A0, but the algorithm will converge more quickly if you choose a number close to the actual square root.

For example, if we want to find the square root of 94, we let N = 94 and A0 = 9.

Step 2: Calculate the first approximating fraction, A1 with the relation

A1 = (A0 + N/A0)/2

In this example, we have

A1 = (9 + 94/9)/2 = 175/18 (≈9.722) after simplifying.

Step 3: Calculate the second approximating fraction, A2 with the relation

A2 = (A1 + N/A1)/2

Continuing the example, we have

A2 = [175/18 + 94/(175/18)]/2 = 61081/6300 (≈9.695) after simplifying.

Step 4: Calculate each successive approximating fraction with the recursion formula

Ak = (Ak-1 + N/Ak-1)/2

You can see why it's called the divide-and-average method. In each step you take the average of the previous answer and N divided by the previous answer.

Although the numerators and denominators become unwieldy, the algorithm converges rapidly. The value of A3 is 7461748561/769620600, which approximates the square root of 94 to 9 digits of accuracy.

Why the Method Works

If L = A is the limit of the sequence, then L must satisfy the equation

L = (L + N/L)/2

Using algebra this reduces to

2L = L + N/L
L = N/L
L² = N
L = √N

To show that the sequence {A0, A1, A2,...} converges (i.e., the limit exists), let {E0, E1, E2,...} be the squared relative errors of each term Ak. That is,

Ek = (Ak/√N - 1)².

Since Ak = (Ak-1 + N/Ak-1)/2 and Ak = √N(√Ek + 1), you can use a bit of algebra to derive a recurrence relation for Ek:

Ek = Ek-1²/[4(√Ek-1 + 1)²].

This is a decreasing sequence whose limit is 0, therefore the sequence {A0, A1, A2,...} converges, and its limit is √N.

© Had2Know 2010