Faster Cube Root II

Yesterday's post discussed an easily calculated cube root approximation with cubic convergence. More spelunking led me to realize the function is the result of a root-finding method known as Halley's method (the fellow with the comet named after him). So it's actually quite old, and, it seems, over the years it has been rediscovered a few times and attributed to others (Lambert, Bailey, etc).

If I ever studied Halley's method, I don't remember doing so. A major strength is that it does exhibit cubic convergence (in contrast to Newton's quadratic convergence). Even if it requires more ops per iteration than Newton's method, an iteration of either method requires a divide. In my experience, there are cases where Halley's method can pay off.

Here's the Wikipedia entry on it: Halley's method.

Halley's method:

x_n+1 = x_n - 2f(x_n)f'(x_n) / (2 (f'(x_n)² - f(x_n)f''(x_n))

In the case of the cube root of R:

f(x) = x³ - R
f'(x) = 3x²
f''(x) = 6x

Plugging them into Halley:

x_n+1 = x - (6x²)(x³-R) / (18x⁴ - 6x(x³-R))

Which simplifies to:

x_n+1 = (2xR + x⁴) / (R + 2x³)

And it's only a little shuffling to get to the function I posted.

The next post looks at coming up with an initial guess for cube root.