 cube root

(algorithm)

Definition: This describes a "long hand" or manual method of calculating or extracting cube roots. Calculation of a cube root by hand is similar to long-hand division or manual square root.

Suppose you need to find the cube root of 55,742,968. Set up a "division" with the number under the radical. Mark off triples of digits, starting from the decimal point and working left. (The decimal point is a period (.), and commas (,) mark triples of digits.)

____________
\/ 55,742,968.
Look at the leftmost digit(s) (55 in this case). What is the largest number whose cube is less than or equal to it? It is 3, whose cube is 27. Write 3 above, write the cube below and subtract.
__3_________
\/ 55,742,968.
-27
----
28
Now bring down the next three digits (742).
__3_________
\/ 55,742,968.
-27
----
28742
Coming up with the next "divisor" is more involved than for square roots. First bring down 3 times the square of the number on top (3 × 3²=27) leaving room for two more digits (27_ _).
__3_________
\/ 55,742,968.
-27
----
27_ _) 28742
What is the largest number that we can put in the next position and multiply times the divisor and still be less than or equal to what we have? (Algebraically, what is d such that d × 2700 ≤ 28742?) 10 might work (since 10 × 2700 = 27000), but we can only use a single digit, so we'll try 9.
__3___9_____
\/ 55,742,968.
-27
----
27_ _) 28742
The second step in making the divisor is adding 3 times the previous number on top (3) times the last digit (9) times 10 (3 × 3 × 9 = 81 × 10 = 810) and the square of the last digit (9² = 81).
2700
810
+ 81
-----
3591
Our new divisor is 3591.
__3___9_____
\/ 55,742,968.
-27
----
3591) 28742
Multiply by the last digit (9 × 3591 = 32319) and subtract. But that is too big! So we'll try 8 as the next digit instead.
__3___8_____
\/ 55,742,968.
-27
----
27_ _) 28742
We repeat the second step of adding 3 times the previous number on top (3) times the last digit (8) times 10 (3 × 3 × 8 = 72 × 10 = 720) and the square of the last digit (8² = 64).
2700
720
+ 64
-----
3484
Our new divisor is 3484.
__3___8_____
\/ 55,742,968.
-27
----
3484) 28742
Now multiply by the last digit (8 × 3484 = 27872) and subtract.
__3___8_____
\/ 55,742,968.
-27
----
3484) 28742
-27872
------
870
We are ready to start over on the next digit. Bring down the next three digits. The divisor starts as 3 times the square of the number on top (3 × 38²=4332) leaving room for two more digits (4332_ _).
__3___8_____
\/ 55,742,968.
-27
----
3484) 28742
-27872
------
4332_ _) 870968
It looks like 2 is the next digit.
__3___8___2_
\/ 55,742,968.
-27
----
3484) 28742
-27872
------
4332_ _) 870968
Add 3 times the previous number on top (38) times the last digit (2) times 10 (3 × 38 × 2 = 228 × 10 = 2280) and the square of the last digit (2² = 4).
433200
2280
+ 4
-------
435484
Our new divisor is 435484.
__3___8___2_
\/ 55,742,968.
-27
----
3484) 28742
-27872
------
435484 ) 870968
Now multiply by the last digit (2 × 435484 = 870968) and subtract.
__3___8___2_
\/ 55,742,968.
-27
----
3484) 28742
-27872
------
435484 ) 870968
-870968
-------
0

So the cube root of 55742968 is 382. You can continue to get as many decimal places as you need: just bring down more triples of zeros.

Why does this work?

Consider (10A + B)³ = 1000A³ + 3 × 100A²B + 3 × 10AB² + B³ and think about finding the volume of a cube.

The volume of the three thin plates is 3 × 100A²B. The volume of the three skinny sticks is 3 × 10AB². The tiny cube is B³. If we know A and the volume of the cube, S, what B should we choose?

We previously subtracted A³ from S. To scale to 1000A³, we bring down three more digits (a factor of 1000) of the length of S. We write down 3 times A squared (3A²), but shifted two places (100 × 3A² or 3 × 100A²). We estimate B. We add 30 times A times B (30 × AB or 3 × 10AB) and B squared. Multiplying that by B gives us 3 × 100A²B + 3 × 10AB² + B³. When we subtract that from the remainder (remember we already subtracted A³), we have subtracted exactly (10A + B)³. That is, we have improved our knowledge of the cube root by one digit, B.

We take whatever remains, scale again by 1000, by bringing down three more digits, and repeat the process.

Note: In computers and hand-held calculators, square root, sine, cosine, and other transcendental functions are calculated with sophisticated functions, such as Taylor series, CORDIC, or Newton-Raphson method, sometimes called Newton's method.

Author: PEB

Implementation

GAMS Class C2 has many implementations of powers, roots, and reciprocals (C and Fortran).