Followup: How do I optimize this Java cube root function for BigInteger?
I think your final solution is on the right path.

Just to be clear, I'm assuming you want the integral part of the cube root, i.e. for a given \$n\$, cbrt(n) will return the integer \$m\$ such that \$m^3 \leq n &lt; (m + 1)^3\$. I'm also assuming you only care about positive inputs.

Here is the code I posted in a comment on the previous question, with an improved initial estimate. Inspired by There are Only Four Billion Floats -- So Test Them All!, I have tested it successfully on all integers in the range [1, Integer.MAX_VALUE) (took about 40m, by the way).

private static final BigInteger THREE = BigInteger.valueOf(3);

private static BigInteger cubeRoot(BigInteger n) {
    // Using Newton's method, we approximate the cube root
    // of n by the sequence:
    // x_{i + 1} = \frac{1}{3} \left( \frac{n}{x_i^2} + 2 x_i \right).
    // See http://en.wikipedia.org/wiki/Cube_root#Numerical_methods.
    //
    // Implementation based on Section 1.7.1 of
    // "A Course in Computational Algebraic Number Theory"
    // by Henri Cohen.
    BigInteger x = BigInteger.ZERO.setBit(n.bitLength() / 3 + 1);
    while (true) {
        BigInteger y = x.shiftLeft(1).add(n.divide(x.multiply(x))).divide(THREE);
        if (y.compareTo(x) &gt;= 0) {
            break;
        }

        x = y;
    }

    return x;
}


The test code:

for (int i = 1; i &lt; Integer.MAX_VALUE; i++) {
    // Report progress.
    if (i % 1000000 == 0) {
        System.out.printf("%d%n", i);
    }

    BigInteger n = BigInteger.valueOf(i);
    BigInteger m = cubeRoot(n);

    BigInteger lower = m.pow(3);
    BigInteger upper = m.add(BigInteger.ONE).pow(3);

    if (lower.compareTo(n) &lt;= 0 &amp;&amp; n.compareTo(upper) &lt; 0) {
        continue;
    }

    System.err.printf("Error for input %s: Got %s%n", n, m);
    System.err.printf("Expected m^3 &lt;= %s &lt; (m + 1)^3%n", n);
    System.err.printf("But m^3 = %s, (m + 1)^3 = %s%n", lower, upper);
}