# 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_{0}. You can pick any number for A_{0}, 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_{0} = 9.

**Step 2:** Calculate the first approximating fraction, A_{1} with the relation

A_{1} = (A_{0} + N/A_{0})/2

In this example, we have

A_{1} = (9 + 94/9)/2 = 175/18 (≈9.722) after simplifying.

**Step 3:** Calculate the second approximating fraction, A_{2} with the relation

A_{2} = (A_{1} + N/A_{1})/2

Continuing the example, we have

A_{2} = [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_{3} 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

_{0}, A

_{1}, A

_{2},...} converges (i.e., the limit exists), let {E

_{0}, E

_{1}, E

_{2},...} 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

_{0}, A

_{1}, A

_{2},...} converges, and its limit is √N.

© *Had2Know 2010
*