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


Why the Cube-root Algorithm works

To show why the cube-root 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 3n-2 to 3n, inclusive, has n digits in the integer part of its cube-root. Thus, for instance, for n=1, each of the numbers 1 to 999 has a single digit in the integer part of its cube-root. So why does the cube-root 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), 911251/3 has 2 digits, say a1a0, in the integer part, by Proposition 2. That is, (a1a0)3 is the largest cube not exceeding 91125.
But, by Proposition 1, (a1a0)3 = 103a13 + (30 a1(a1a0)+ a02)a0.
That is,
91,125 ≥ (a1a0)3 = 103a13 + (30 a1(a1a0)+ a02)a0.      ------ Step (*)
In particular, 91,125 ≥ 103a13.
So, 91,000 ≥ 103a13. That is, a13 ≤ 91.

Suppose a13 is not the largest cube not exceeding 91, say 91 ≥ b13 > a13. The first part of this inequality is 91 ≥ b13 which implies (10b1)3 < 91,125. The second part of the inequality is (b1)3 > (a1)3 which gives b1 > a1 and so 10b1 > a1a0 or (10b1)3 > (a1a0)3. This means 91,125 > (10b1)3 > (a1a0)3, which contradicts the assumption that (a1a0)3 is the largest cube not exceeding 91,125. Thus (a1)3 is indeed the largest cube not exceeding 91. That is, a1 = 4. But then, from Step (*) above,
91,125 - 64,000 ≥ (30 × 4 × (4a0) + a02)a0, where 4a0 denotes the integer whose units digit is a0 and tens digit is 4.
Suppose now that there exists a0' such that 91,125 - 64,000 ≥ (30 × 4 × (4a0') + a0'2)a0' and a0' > a0.
But then, 91,125 ≥ (a1a0')3 > (a1a0)3, which contradicts the assumption that (a1a0)3 is the largest cube not exceeding 91,125.
So, a0 is the largest integer such that (91,125 - 64,000) - (30 × 4 × (4a0) + a02)a0) ≥ 0. That is, a0 = 5.
Since (91,125 - 64,000) - (30 × 4 × (4a0) + a02)a0) = 0, the cube-root 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 103i that appear on the right of the equation in Proposition 1 are taken care of by subracting the quantity Qi whose positional value is 103i × Qi. This implements the decomposition in terms of 103i((30 × an...ai+1 × anan-1...ai) + ai2)ai appearing on the right side of the equation in Proposition 1. Another way of seeing this is that i-1 groups of three digits each are brought down after the subtraction of (30 × an...ai+1 × anan-1...ai) + ai2)ai so that the subtracted quantity has a place value of 103i.

What if we are looking for the cube-root 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 cube-root must be of the form
x = anan-1...a1a0.a-1a-2...a-k, say, and, so, equals 10-k(anan-1...a1a0a-1a-2...a-k).
Let n+k = m.
Rename ai as ak+i, i = n, n-1,...,2,1,0,-1,...,-k.
Then, x = 10-k(amam-1...akak-1...a0) and, from Proposition 2,
.
This means that, in finding the cube-root 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 (10kx)3. Therefore, the value of x which is the cube-root of the given number is obtained up to k decimal digits by dividing the number obtained in the division process by 10k, or by inserting a decimal point just before the last k digits of the "quotient." We have shown the following.

Proposition 3 (The cube-root algorithm)
Let N be a number in decimal representation. The cube-root of N is obtained by the following procedure.
    (1) Beginning at the decimal point, parse N in groups Ai, 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
AnAn-1...A1A0.A-1A-2...Ak-1A-k, where the left-most group An on the left of the decimal point and the right-most 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 an so that (an)3 is the largest cube not exceeding An. Let Bn-1 be the number obtained by concatenating
(An - an3) with An-1. That is, Bn-1 = (An - an3)An-1.
    (3) For i = n-1 to -k, choose ai, being the largest single-digit number, so that ((30 × an...ai+1 × anan-1...ai) + ai2)ai does not exceed Bi. Let Bi-1 = (Bi - ((30 × an...ai+1 × anan-1...ai) + ai2)ai)Ai.
    (4) Then the cube-root of N is anan-1...a1a0.a-1a-2...a-k.

Observe that when N is an integer, Ai = 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