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 cube-root 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 square-root algorithm that uses the divide-and-average technique to reach a minimum error value. Before the cube-root 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 value--in 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 root-actual 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 limit--the cube root of 0--you 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 1012 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.|