7
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you post an input for which the BigInteger-only version does not terminate? \$\endgroup\$ – mjolka Jun 30 '14 at 4:15
  • \$\begingroup\$ @mjolka The number 5. \$\endgroup\$ – Brian J. Fink Jul 1 '14 at 2:52
  • \$\begingroup\$ @mjolka It hangs on 4, actually. \$\endgroup\$ – Brian J. Fink Jul 1 '14 at 3:24
  • \$\begingroup\$ I think you can terminate when r <= s. See ideone.com/QH2cFe. \$\endgroup\$ – mjolka Jul 1 '14 at 4:03
  • \$\begingroup\$ @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. \$\endgroup\$ – Brian J. Fink Jul 10 '14 at 20:22
10
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ My precision with the number I'm cube-rooting must be exact! \$\endgroup\$ – Brian J. Fink Jul 1 '14 at 2:45
  • \$\begingroup\$ I'm testing for perfect cubes and/or sums of positive cubes. \$\endgroup\$ – Brian J. Fink Jul 1 '14 at 2:47
  • \$\begingroup\$ Incidentally, my question was about optimization, not readability! \$\endgroup\$ – Brian J. Fink Jul 1 '14 at 3:04
  • \$\begingroup\$ @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. \$\endgroup\$ – Simon Forsberg Jul 1 '14 at 9:47
  • \$\begingroup\$ @BrianJ.Fink How big numbers do you want to know the cube-rooting of? \$\endgroup\$ – Simon Forsberg Jul 1 '14 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.