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 A₀. You can pick any number for A₀, 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 A₀ = 9.

Step 2: Calculate the first approximating fraction, A₁ with the relation

A₁ = (A₀ + N/A₀)/2

In this example, we have

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

Step 3: Calculate the second approximating fraction, A₂ with the relation

A₂ = (A₁ + N/A₁)/2

Continuing the example, we have

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

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

A_k = (A_k-1 + N/A_k-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 A₃ 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 {A₀, A₁, A₂,...} converges (i.e., the limit exists), let {E₀, E₁, E₂,...} be the squared relative errors of each term A_k. That is,

E_k = (A_k/√N - 1)².

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

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

This is a decreasing sequence whose limit is 0, therefore the sequence {A₀, A₁, A₂,...} converges, and its limit is √N.

© Had2Know 2010