01.15.98 Algorithm extracts cube root
EDN Staff
January 15, 1998


January 15, 1998 Algorithm extracts cube rootJohn T Hannon Jr, Philips Consumer Electronics Corp, Knoxville, TN The C routine in Listing 1 generates the cube root of either a positive or a negative number. The number can range from a small fraction to greater than 1 billion. Note that this idea is irrelevant for a PC, which includes a math library with the compiler and produces a more accurate result with less effort. However, this idea is useful if you use a processor for which you don't have a math library. The main routine inputs a number from the keyboard and calls the cuberoot function. After calculating the cube root, the routine prints the result on the screen. The routine then recalculates the cube of this cuberoot answer and prints this number on the screen so you can compare the accuracy of the result with the original number. Five decimal places are set up for the print command to allow an accurate comparison. This algorithm is similar to the squareroot algorithm that uses the divideandaverage technique to reach a minimum error value. Before the cuberoot operation begins, the routine determines if the number is positive or negative. If the value is negative, the program sets a flag so the returned root value can be set to a negative value. To start the process, the routine sets up an error value and assigns an initial value for the integer root. The error value for this function is 0.00001, and the initial value of root is 2.0. The routine squares this value and divides it into the given number. The routine then adds the result to the original value of root and divides this sum by 2 to generate the new value of root. This process continues until the absolute value of the difference between the cube of the value of root and the given number is less than the error valuein this case, 0.00001. For some values, this algorithm approaches but never reaches the set error. Thus, the routine increments a counter after each iteration. If the counter reaches the maximum set count before the routine finds the minimum error, the function ends and returns the value of root. If the original number was negative, the routine changes the cube root to a negative value. With the values in Listing 1, the accuracy for numbers from 0.1 to greater than 1 billion is better than 0.001%. For numbers less than 0.2, the accuracy is slightly lower. However, this accuracy difference is a result of the error value that you use in the calculation. By setting the error value (float variable error) to a smaller value, such as 0.000001, the accuracy for very small numbers can also approach this value. Two other factors affect the accuracy: the number of bits the processor uses for floating point numbers, and the size of the original number. For numbers with small absolute values, the variable error controls the accuracy. The accuracy, which is (calculated rootactual root)/actual root, is approximately equal to error variable/3xoriginal number. So, with error set to 0.00001, the accuracy is about 0.003% for the cube root of 0.1, 0.03% for the cube root of 0.01, 0.3% for the cube root of 0.001, and so forth. In the limitthe cube root of 0you can't divide by 0 to find percent accuracy, but the actual root that the program calculates is 0.0156250. For numbers with large absolute values, the number of iterations determines the accuracy. For instance, the algorithm calculates the cube root of 10^{12} as 10083.87109 after 25 iterations and as10000.00000 after 45 iterations. (DI #2144) 

 EDN Access  Feedback  Table of Contents  

Copyright c 1997 EDN Magazine, EDN Access. EDN is a registered trademark of Reed Properties Inc, used under license. EDN is published by Cahners Publishing Company, a unit of Reed Elsevier Inc. 
Understanding SSD overprovisioning
Equations and Impacts of Setup and Hold Time
ARM flexes from servers to wearables
Embedded Systems Architecture, Device Drivers  Part 1: Interrupt Handling
Singlecycle logarithms & antilogs
Automotive System & Software Development Challenges – Part 1
How FPGAs and multicore CPUs are changing embedded design
Memory Hierarchy Design  Part 1. Basics of Memory Hierarchies
The future of computers  Part 1: Multicore and the Memory Wall
FEATURED RESOURCES