How do I optimize this Java cube root function for BigInteger?

Question

I find that this function is one of the biggest causes of slow program execution. I can write a square root version with BigInteger only, but with the cube root, the algorithm sometimes gets caught in an endless loop unless I also use BigDecimal, because the values of r and s never reach equilibrium. I've already used tricks like leftShift to multiply by 2 and s.multiply(s) in place of s.pow(2) to make it faster, but having to use BigDecimal is still slowing it down. Any idea how I could approach this problem?

public static BigDecimal THREE_D=BigDecimal.valueOf(3);

public static int UP=BigDecimal.ROUND_HALF_UP;

// other statements

public static BigInteger cbrt(BigInteger n)
{
 BigDecimal m=new BigDecimal(n);                          // BigDecimal copy
 BigInteger r=BigInteger.ZERO.setBit(n.bitLength()/3);    // initial estimate
 for(BigDecimal s=BigDecimal.ZERO;                        // different from r
     !r.equals(s.toBigInteger());                         // loop test: does r=s?
     s=new BigDecimal(r),r=new BigDecimal(r.shiftLeft(1)) // Convert to BigDecimal,
      .add(m.divide(s.multiply(s),UP))                    // do the tricky division,
      .divide(THREE_D,UP).toBigInteger());                // and convert back.
 return r;                                                // return the value
}

Edit: Followup to this question can be found here.

Answer 1

Your current code is totally unreadable and very hard to understand.

For vs. While

You've literally packed everything inside a for-loop without a body. WHY!?

This would be a lot more readable using a while-loop.

BigDecimal s = BigDecimal.ZERO;
while (!result.equals(s.toBigInteger())) {
    s = new BigDecimal(result);

    // Convert to BigDecimal, do the tricky division,
    // and convert back.
    BigDecimal temp0 = new BigDecimal(result.shiftLeft(1));
    BigDecimal temp1 = temp0.add(valueCopy.divide(s.multiply(s), UP));
    BigDecimal temp2 = temp1.divide(THREE_D, UP);
    result = temp2.toBigInteger();
    iterations++;
}

The temp0, temp1, and temp2 stuff can be written on one line, but I thought it deserved to be broken up among a few lines to be more readable.

---

Comments

Some unnecessary comments:

// other statements
// BigDecimal copy
// return the value

Please don't add comments about what you're doing, add comments for explaining why you are doing it. The code often tells us what you're doing.

Explaining what you're doing is OK for totally non-understandable parts though, these comments are helpful:

// Convert to BigDecimal,
// do the tricky division,
// and convert back.

---

Variable names

BigDecimal s;
BigInteger r;
BigDecimal m;

Please don't use one-letter variable names!

Explain what you're variable name is used for r seems to be for result, which is a much better variable name than r. I don't understand what s and m are used for exactly so I can't come up with a better name for those. Admittedly, my tempX names used above are also bad names, I hope you can come up with better ones.

---

Another approach:

Your code is already faster than anything I would be able to write by hand. I don't know if you're aware of it already or not, but there is however an in-built Java method you can use for this job - If you're willing to drop some precision for huge numbers.

I tried to compute the cubic root of 4.781260832191688e49

One in-built method call returns 3.6295056667577016E16.

Your code returns 36295056667577090

So there's a difference of 74, for a number of the order 4*10^49 I think that's pretty good.

The correct result with a lot of precision is:

3.6295056667577090244467986066615526182629927485862843007... × 10^16

So what's the secret method call then you ask?

Math.pow(4.781260832191688e49, 1.0 / 3.0);