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

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.

• Can you post an input for which the BigInteger-only version does not terminate? – mjolka Jun 30 '14 at 4:15
• @mjolka The number 5. – Brian J. Fink Jul 1 '14 at 2:52
• @mjolka It hangs on 4, actually. – Brian J. Fink Jul 1 '14 at 3:24
• I think you can terminate when r <= s. See ideone.com/QH2cFe. – mjolka Jul 1 '14 at 4:03
• @mjolka I discovered that your algorithm does not work on all numbers, not even perfect cubes. Try it on 111(cubed)=1367631. I guarantee you'll get 113 as your answer. – Brian J. Fink Jul 10 '14 at 20:22

### 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 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.

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


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);

• My precision with the number I'm cube-rooting must be exact! – Brian J. Fink Jul 1 '14 at 2:45
• I'm testing for perfect cubes and/or sums of positive cubes. – Brian J. Fink Jul 1 '14 at 2:47
• Incidentally, my question was about optimization, not readability! – Brian J. Fink Jul 1 '14 at 3:04
• @BrianJ.Fink Incidentally, it's hard to help you improve performance when the code's unreadable. Besides, one thing does not have to exclude the other. – Simon Forsberg Jul 1 '14 at 9:47
• @BrianJ.Fink How big numbers do you want to know the cube-rooting of? – Simon Forsberg Jul 1 '14 at 9:48