Hacker's Delight

11-2. Integer Cube Root

For cube roots, Newton’s method does not work out very well. The iterative formula is a bit complex:

and there is of course the problem of getting a good starting value x₀.

However, there is a hardware algorithm, similar to the hardware algorithm for square root, that is not too bad for software. It is shown in Figure 11-5.

Figure 11-5. Integer cube root, hardware algorithm.

int icbrt(unsigned x) { int s; unsigned y, b; s = 30; y = 0; while(s >= 0) { // Do 11 times. y = 2*y; b = (3*y*(y + 1) + 1) << s; s = s - 3; if (x >= b) { x = x - b; y = y + 1; } } return y; }

The three add’s of 1 can be replaced by or’s of 1, ...