Numerical Methods
Newton's method is an Iterative method that can be used to calculate the cube root. For real floating point numbers this method reduces to the following iterative algorithm to produce successively better approximations of the cube root of :
The method is simply averaging three factors chosen such that at each iteration.
Halley's method improves upon this with an algorithm that converges more quickly with each step, albeit consuming more multiplication operations:
With either method a poor initial approximation of can give very poor algorithm performance, and coming up with a good initial approximation is somewhat of a black art. Some implementations manipulate the exponent bits of the floating point number; i.e. they arrive at an initial approximation by dividing the exponent by 3. This has the disadvantage of requiring knowledge of the internal representation of the floating point number, and therefore a single implementation is not guaranteed to work across all computing platforms.
Also useful is this generalized continued fraction, based on the nth root method:
If x is a good first approximation to the cube root of z and y = z − x3, then:
The second equation combines each pair of fractions from the first into a single fraction, thus doubling the speed of convergence. The advantage is that x and y are only computed once.
Read more about this topic: Cube Root
Famous quotes containing the words numerical and/or methods:
“The terrible tabulation of the French statists brings every piece of whim and humor to be reducible also to exact numerical ratios. If one man in twenty thousand, or in thirty thousand, eats shoes, or marries his grandmother, then, in every twenty thousand, or thirty thousand, is found one man who eats shoes, or marries his grandmother.”
—Ralph Waldo Emerson (1803–1882)
“The comparison between Coleridge and Johnson is obvious in so far as each held sway chiefly by the power of his tongue. The difference between their methods is so marked that it is tempting, but also unnecessary, to judge one to be inferior to the other. Johnson was robust, combative, and concrete; Coleridge was the opposite. The contrast was perhaps in his mind when he said of Johnson: “his bow-wow manner must have had a good deal to do with the effect produced.””
—Virginia Woolf (1882–1941)