
Useful Computational Methods 

Cuberoot algorithms


The cube root of a number N is a number b satisfying b^{3} = N. Now, each real number N has three cube roots. One of them is the real number b. The others are b(e^{2pi/3}) and b(e^{4pi/3}), the complex roots, of which one learns in high school. In any case, it is sufficient to obtain the real root b since the other roots then follow as described above.
The number N is said to be a perfect cube if b is an integer such that b^{3} = N. If N is a negative real number then b is a negative real number so that, we can, in such cases too, assume N to be a positive real number and after obtaining the cube root, change its sign. Thus, without loss of generality, we assume N to be a positive real number.
If a perfect cube has only three or four digits, it is not inconvenient to try to get its cube root by looking at cubes of integers smaller than 22  the cube of 22 exceeds 10000.
If the number is not a perfect cube, the method is still useful in that we can find two consecutive integers between which the cube root lies. Then we can use a guess and check to improve the approximation, but the method then becomes tedious.
Here we explain a longdivisionlike algorithm that rapidly obtains cube roots to any precision. The method has been used as early as 1600 A.D. and was, therefore, discovered not later than that date. This algorithm, while it is easy to find cube roots using it, is little known.
All the other methods for obtaining cube roots employ successive approximations.
The Longdivisionlike cuberoot Algorithm
This is the handcalculation that proceeds in a manner similar to that of the longdivisionlike squareroot algorithm. It can handle very large numbers with ease. The method has two advantages over all other methods for cube roots: (1) the value of rational fractions are obtained in a finite number of steps, and (2) each step correctly obtains a single digit of the answer; that is, in n steps it obtains n correct digits of the answer, the nth digit being the one produced by the nth step.
Let us find the cube root of 12812904. First we parse the number in groups of three, beginning from the units digit, going left, and from the tenths digit, going right. Thus 12812904 is written 12,812,904. The leftmost group after parsing yields the number 12. Then we ask for the largest integer whose cube does not exceed 12. The integer is 2 and its cube is 8. Subtract 8 from 12 and bring down 812. So we have the following.
Here, the radical sign does not mean square root; rather, it means cube root.
The digit 2 thus obtained is our a_{n}. Next we look for the largest digit a_{n1} so that (30 ´ a_{n} ´ a_{n}a_{n1} + (a_{n1})^{2})a_{n1} does not exceed 4,812. a_{n1} = 3.
That is, (30 ´ 2 ´ 23 + 3^{2})3 = 4167 does not exceed 4812, whereas (30 ´ 2 ´ 24 + 4^{2})4 is 11588 which exceeds 4812.
Now we subtract 4167 from 4812 and bring down the next group of three digits. So we have the following.
Next we look for a_{n2}. It is the largest digit so that (30 ´ 23 ´ 23a_{n2} + a_{n2}^{2})a_{n2}, where 23a_{n2} denotes not the product of 23 and a_{n2}, rather the threedigit integer whose units digit is a_{n2}, tens digit is 3, and hundreds digit is 2. By trial and error, we find that a_{n2} = 4. In fact
(30 ´ 23 ´ 234 + 4^{2})4 = 645,904. With no more group of digits remaining to be brought down, we are finished since there is no remainder. So the cube root of 12812904 is 234.
What if the original number were 12812905. Then there would be a remainder, namely 1. So we bring down the next group of three digits which is 000 and ask for the largest digit a_{1} so that (30 ´ 234 ´ 234a_{1} + a_{1}^{2})a_{1} does not exceed 1000. The largest digit is 0 and (30 ´ 234 ´ 2340 + 0^{2})0 = 0, which we subract from 1000. Next, we bring down the next group of three digits which is also 000 and ask for the largest digit a_{2} so that
(30 ´ 2340 ´ 2340a_{2} + a_{2}^{2})a_{2} does not exceed 1,000,000. a_{2} = 0. Next we ask for the largest digit a_{3} so that
(30 ´ 23400 ´ 23400a_{3} + a_{3}^{2})a_{3} does not exceed 1,000,000,000. a_{3} = 1. We have reached the approximation that the cube root of 12812905 is 234.001... and greater precision is attained by continuing from
Note that in the first step of the algorithm, we ask for the largest integer whose cube does not exceed the leftmost group of digits in the parsing of the original number. In each of the ensuing steps we ask a different question.
That is, in the kth step, k > 1, we look for the largest integer a_{nk+1} so that the numerical value of the quantity
(30 ´ a_{n}a_{n1}...a_{nk+2} ´ a_{n}a_{n1}...a_{nk+2}a_{nk+1} + a_{nk+1}^{2})a_{nk+1} does not exceed the number obtained by concatenating, the remainder after k1 steps, with the kth group from the left in the parsing.
For instance, when k=2, the quantity in question is
(30 ´ a_{n} ´ a_{n}a_{n1} + a_{n1}^{2})a_{n1}, where a_{n}a_{n1} is the twodigit integer whose units digit is a_{n1}.
The method works the same way also for numbers less than 1. Let us find the cube root of 0.015625. First we parse it as 0.015,625 and ask for the largest integer a_{1} whose cube does not exceed 15. The integer is 2. This gives 0.2 as the first approximation of the cube root of 0.015625. Then we subtract 8 from 15 and bring down 625. Then we ask for the largest integer a_{2} so that
(30 ´ 2 ´ 2a_{2} + a_{2}^{2})a_{2} does not exceed 7625, where 2a_{2} denotes not the product of 2 and a_{2} but the integer whose units digit is a_{2} and the tens digit is 2. Now, (30 ´ 2 ´ 25 + 5^{2}) = 7625. Since the remainder is zero, the cube root of 0.015625 is 0.25. The procedure is summarized in the diagram below.
If you wish to know why the algorithm works, please follow the link below.
Why the longdivisionlike cube root algorithm works
Ü BACK
MathPath  "BRIGHT AND EARLY"
Send suggestions to webmaster@mathpath.org
Copyright © 2001 MathPath
Last updated  November 8, 2003

