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).

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).

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).

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.

See also square root.

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. This lesson explains, for instance, possible difficulties in convergence.

Author: PEB

Implementation

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

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 17 August 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "cube root", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 August 2009. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/cubeRoot.html