
Useful Computational Methods 

Cube roots via a modified Babylonian Algorithm


The Babylonian Algorithm for the square root of a number N is
x_{n+1} = (x_{n} + N/x_{n})/2, where x_{n+1} is the n+1th approximation to the square root, obtained from x_{n} which is the nth approximation.
The Babylonian Algorithm can be modified to obtain cube roots to give the formula
x_{n+1} = (2x_{n} + N/x_{n}^{2})/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 x_{0} such that
x_{0} < N^{1/3}.
Then
1 < N^{1/3}/ x_{0}
Therefore
N^{1/3} < N^{1/3}/x_{0} . N^{1/3}/x_{0} . N^{1/3} = N/x_{0}^{2}.
So
x_{0} < N^{1/3} < N/x_{0}^{2}.
We have the following picture.
x_{0}  N^{1/3}  N/x_{0}^{2}
Since the desired number is N^{1/3} and it lies between x_{0} and N/x_{0}^{2} we take x_{1} to be the number midway between x_{0} and N/x_{0}^{2}, which is (x_{0} + N/x_{0}^{2})/2.
However, it turns out that a better approximation is
(2/3)x_{0} +(1/3) N/x_{0}^{2}
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 Rootformulas" for the extended Babylonian Algorithm. (We will include this article soon and provide the link.)
So the Babylonian Algorithm extended to cube roots is
x_{n+1} = (2x_{n} +N/x_{n}^{2})/3
Let us find the cube root of 5.
Since 1^{3} = 1 and 2^{3} = 8, we let x_{0} = 1. Then
x_{n}    Error = x_{n}  N 
x_{1}  = ((2)1 + 5/1)/3  = 2.333...  
x_{2}  = ((2)(7/3) + 5/(7/3)^{2})/3  = 2.3797...  
x_{3}  = 1.880780453...  
x_{4}  = 1.725018...  
x_{5}  = 1.710106733...   0.0001307... 
x_{6}  = 1.709975957...   0.0000001... 
A calculator gives the value 5^{1/3} = 1.709975947...
The "Error" in the nth approximation is the absolute value of x_{n}  N which in this situtaion, where x_{n} > N,
is x_{n}  N. This is given in the last column. Notice that we have given the error values only for x_{5} and x_{6}, 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 squareroots 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 x_{0} < N^{1/3}. This is not necessary. The derivation follows similarly for the case x_{0} < N^{1/3}. For instance, in attempting to find 5^{1/3}, we could have started with x_{0} = 2. In fact, starting with 2 would have given us x_{1} = 1.75, which is closer to the actual value than the x_{1}, x_{2} and x_{3} when we started with x_{0} = 1.
This tells that we could start with arbitrary values close to N^{1/3}.
Try x_{0} = 3/2.
Then x_{1} = 1.740... which is better than what we obtained with x_{0} = 1 and x_{1} = 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 x_{0} > 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.
REFERENCES
R.J.Knill, A Modified Babylonian Algorithm, American Mathematical Monthly, 99(1992), pp. 734737
Ü BACK
MathPath  "BRIGHT AND EARLY"
Send suggestions to webmaster@mathpath.org
Copyright © 2001 MathPath
Last updated  November 8, 2003

