A summer program and resource for middle school students showing high promise in mathematics

Useful Computational Methods

Cube roots via a modified Babylonian Algorithm

The Babylonian Algorithm for the square root of a number N is
xn+1 = (xn + N/xn)/2, where xn+1 is the n+1-th approximation to the square root, obtained from xn which is the n-th approximation. The Babylonian Algorithm can be modified to obtain cube roots to give the formula
xn+1 = (2xn + N/xn2)/3
Here is the derivation, which you may skip to go on to the next topic.

Suppose we wish to find the cube root of a number N. We start with a close guess x0 such that
x0 < N1/3.
Then 1 < N1/3/ x0
Therefore N1/3 < N1/3/x0 . N1/3/x0 . N1/3 = N/x02.
x0 < N1/3 < N/x02.
We have the following picture.

x0 ---- N1/3 ----------- N/x02

Since the desired number is N1/3 and it lies between x0 and N/x02 we take x1 to be the number midway between x0 and N/x02, which is (x0 + N/x02)/2. However, it turns out that a better approximation is
(2/3)x0 +(1/3) N/x02
which is the formula we stated above.
The reason why this is a better approximation will take us too far from our main theme. However, if you wish to purse the reason later, you will find it under the link "Weighting to Obtain the Root-formulas" for the extended Babylonian Algorithm. (We will include this article soon and provide the link.)

So the Babylonian Algorithm extended to cube roots is
xn+1 = (2xn +N/xn2)/3

Let us find the cube root of 5.
Since 13 = 1 and 23 = 8, we let x0 = 1. Then

xnError = xn - N
x1= ((2)1 + 5/1)/3= 2.333...
x2= ((2)(7/3) + 5/(7/3)2)/3= 2.3797...
x3= 1.880780453...
x4= 1.725018...
x5= 1.710106733...0.0001307...
x6= 1.709975957...0.0000001...

A calculator gives the value 51/3 = 1.709975947...
The "Error" in the n-th approximation is the absolute value of xn - N which in this situtaion, where xn > N, is xn - N. This is given in the last column. Notice that we have given the error values only for x5 and x6, for they illustrate an important characteristic of efficient algorithms. The efficiency of an algorithm is the speed with which it converges to the desired result. In the case of computation of approximations to a value, the speed is measured by the growth with n, for sufficiently large n, of the number of zeros after the decimal in the value of the Error function. In our calculation above, the "sufficiently large value of n" occurs at n = 5. After n = 5, the number of zeros after the decimal point at least doubles at each step. Such algorithms where this occurs are called "quadratically convergent" algorithms. The Babylonian Algorithm for square-roots and the extended Babylonian Algorithm for cube roots are quadratically convergent. Quadratically convergent algorithms are among the class of what are known as fast algorithms.

You would have noticed that we assumed x0 < N1/3. This is not necessary. The derivation follows similarly for the case x0 < N1/3. For instance, in attempting to find 51/3, we could have started with x0 = 2. In fact, starting with 2 would have given us x1 = 1.75, which is closer to the actual value than the x1, x2 and x3 when we started with x0 = 1. This tells that we could start with arbitrary values close to N1/3.
Try x0 = 3/2.
Then x1 = 1.740... which is better than what we obtained with x0 = 1 and x1 = 2. If you are worried about guessing a close value, you don't have to. It will suffice to use any value so long as x0 > 0. Of'course the farther the guess happens to be, the longer it will take to get the iterations to approach values close to the cube root.

R.J.Knill, A Modified Babylonian Algorithm, American Mathematical Monthly, 99(1992), pp. 734-737




Send suggestions to webmaster@mathpath.org
Copyright © 2001-   MathPath
Last updated - November 8, 2003