


Why the Cuberoot Algorithm works


To show why the cuberoot algorithm works we use Propositions 1 and 2 given below.
To prove the next result, we need the following.
Claim:
According to Proposition 2, an integer having number of digits in the range from 3n2 to 3n, inclusive, has n digits in the integer part of its cuberoot. Thus, for instance, for n=1, each of the numbers 1 to 999 has a single digit in the integer part of its cuberoot. So why does the cuberoot algorithm work?
Let us start with a number, say 91125. Since it has five digits and 5 lies between 3(2)2 and 3(2), 91125^{1/3} has 2 digits, say a_{1}a_{0}, in the integer part, by Proposition 2. That is, (a_{1}a_{0})^{3} is the largest cube not exceeding 91125.
But, by Proposition 1, (a_{1}a_{0})^{3} = 10^{3}a_{1}^{3} + (30 a_{1}(a_{1}a_{0})+ a_{0}^{2})a_{0}.
That is,
91,125 ≥ (a_{1}a_{0})^{3} = 10^{3}a_{1}^{3} + (30 a_{1}(a_{1}a_{0})+ a_{0}^{2})a_{0}.
 Step (*) In particular, 91,125 ≥ 10^{3}a_{1}^{3}.
So, 91,000 ≥ 10^{3}a_{1}^{3}. That is, a_{1}^{3} ≤ 91.
Suppose a_{1}^{3} is not the largest cube not exceeding 91, say 91 ≥ b_{1}^{3} > a_{1}^{3}.
The first part of this inequality is 91 ≥ b_{1}^{3} which implies (10b_{1})^{3} < 91,125.
The second part of the inequality is (b_{1})^{3} > (a_{1})^{3} which gives b_{1} > a_{1} and so 10b_{1} > a_{1}a_{0} or (10b_{1})^{3} > (a_{1}a_{0})^{3}.
This means 91,125 > (10b_{1})^{3} > (a_{1}a_{0})^{3}, which contradicts the assumption that (a_{1}a_{0})^{3} is the largest cube not exceeding 91,125. Thus (a_{1})^{3} is indeed the largest cube not exceeding 91. That is, a_{1} = 4.
But then, from Step (*) above,
91,125  64,000 ≥ (30 × 4 × (4a_{0}) + a_{0}^{2})a_{0}, where 4a_{0} denotes the integer whose units digit is a_{0} and tens digit is 4.
Suppose now that there exists a_{0}' such that
91,125  64,000 ≥ (30 × 4 × (4a_{0}') + a_{0}'^{2})a_{0}' and a_{0}' > a_{0}.
But then, 91,125 ≥ (a_{1}a_{0}')^{3} > (a_{1}a_{0})^{3}, which contradicts the assumption that (a_{1}a_{0})^{3} is the largest cube not exceeding 91,125.
So, a_{0} is the largest integer such that
(91,125  64,000)  (30 × 4 × (4a_{0}) + a_{0}^{2})a_{0}) ≥ 0. That is, a_{0} = 5.
Since (91,125  64,000)  (30 × 4 × (4a_{0}) + a_{0}^{2})a_{0}) = 0, the cuberoot of 91125 is 45.
Observe that, in the "division" process, the subtraction of 64,000 is implemented by subtracting 64 from 91 whose positional value is 91000. By successivley bringing down all groups in the parsing of 91125, we have, in effect, subtracted 64,000 from 91,125. This also illustrates how the
powers 10^{3i} that appear on the right of the equation in Proposition 1 are taken care of by subracting the quantity Q_{i} whose positional value is 10^{3i} × Q_{i}.
This implements the decomposition in terms of 10^{3i}((30 × a_{n}...a_{i+1} × a_{n}a_{n1}...a_{i}) + a_{i}^{2})a_{i} appearing on the right side of the equation in Proposition 1.
Another way of seeing this is that i1 groups of three digits each are brought down after the subtraction of
(30 × a_{n}...a_{i+1} × a_{n}a_{n1}...a_{i}) + a_{i}^{2})a_{i} so that the subtracted quantity has a place value of 10^{3i}.
What if we are looking for the cuberoot of 91126? Then we have a remainder of 1 and so we think of 91126 as 91126.000 and bring down the three zeros. Why?
Since two consecutive integers can not be both perfect cubes, 91126 can not be a perfect cube. So its cuberoot must be of the form
x = a_{n}a_{n1}...a_{1}a_{0}.a_{1}a_{2}...a_{k}, say, and, so, equals
10^{k}(a_{n}a_{n1}...a_{1}a_{0}a_{1}a_{2}...a_{k}).
Let n+k = m.
Rename a_{i} as a_{k+i}, i = n, n1,...,2,1,0,1,...,k.
Then, x = 10^{k}(a_{m}a_{m1}...a_{k}a_{k1}...a_{0}) and, from Proposition 2,
.
This means that, in finding the cuberoot of a number that is not a perfect cube, if all the digits to the left of the decimal point have been brought down in the division process of this algorithm, we continue the process beginning from the immediate right of the decimal point, successively bringing down groups of three digits and each time repeating the "division" as before. After k groups of three digits each are brought down beginning from the digit to the immediate right of the decimal point, we have obtained the cube root of (10^{k}x)^{3}. Therefore, the value of x which is the cuberoot of the given number is obtained up to k decimal digits by dividing the number obtained in the division process by 10^{k}, or by inserting a decimal point just before the last k digits of the "quotient."
We have shown the following.
Proposition 3 (The cuberoot algorithm)
Let N be a number in decimal representation. The cuberoot of N is obtained by the following procedure.
(1) Beginning at the decimal point, parse N in groups A_{i}, i = 0,..,n, of three digits going left from the decimal point and then in groups A_{j}, j = 1,...,k, of three digits going right from the decimal point so that N is given by the concatenation A_{n}A_{n1}...A_{1}A_{0}.A_{1}A_{2}...A_{k1}A_{k}, where the leftmost group A_{n} on the left of the decimal point and the rightmost group A_{k}, on the right of the decimal point, each has one, two or three digits, depending on the number of digits of N.
(2) Choose a_{n} so that (a_{n})^{3} is the largest cube not exceeding A_{n}. Let B_{n1} be the number obtained by concatenating (A_{n}  a_{n}^{3}) with A_{n1}. That is, B_{n1} = (A_{n}  a_{n}^{3})A_{n1}.
(3) For i = n1 to k, choose a_{i}, being the largest singledigit number, so that ((30 × a_{n}...a_{i+1} × a_{n}a_{n1}...a_{i}) + a_{i}^{2})a_{i} does not exceed B_{i}. Let B_{i1} = (B_{i}  ((30 × a_{n}...a_{i+1} × a_{n}a_{n1}...a_{i}) + a_{i}^{2})a_{i})A_{i}.
(4) Then the cuberoot of N is a_{n}a_{n1}...a_{1}a_{0}.a_{1}a_{2}...a_{k}.
Observe that when N is an integer, A_{i} = 000, for i = 1 to k. And when N is an integer that is a perfect cube, B_{1} = 0 as well.
Ü BACK
MathPath  "BRIGHT AND EARLY"
Send suggestions to webmaster@mathpath.org
Copyright © 2001 MathPath
Last updated  June 18, 2003

