Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-4646474

BigInteger.pow() algorithm slow in 1.4.0

    XMLWordPrintable

    Details

    • Type: Enhancement
    • Status: Closed
    • Priority: P4
    • Resolution: Fixed
    • Affects Version/s: 1.4.0
    • Fix Version/s: 8
    • Component/s: core-libs
    • Labels:
    • Subcomponent:
    • Resolved In Build:
      b96
    • CPU:
      x86
    • OS:
      windows_2000
    • Verification:
      Verified

      Backports

        Description

        Name: jl125535 Date: 03/04/2002


        FULL PRODUCT VERSION :
        java version "1.4.0"
        Java(TM) 2 Runtime Environment, Standard Edition (build 1.4.0-b92)
        Java HotSpot(TM) Client VM (build 1.4.0-b92, mixed mode)

        FULL OPERATING SYSTEM VERSION :
        Microsoft Windows 2000 [Version 5.00.2195]


        ADDITIONAL OPERATING SYSTEMS :
        All


        A DESCRIPTION OF THE PROBLEM :
        The algorithm used by BigInteger.pow(int exponent) is
        extremely slow for large exponents, making it unusable for
        serious mathematical work.

        For example, calculating the value of the largest
        currently-known Mersenne prime, 2^13466917 - 1, takes about
        104 minutes on an 800 MHz Pentium III.

        This is not the same bug as 4449911; that bug indicates a
        regression when porting a C library to Java for JDK 1.3.
        The regression was fixed. This bug is to address the fact
        that non-optimal *algorithms* are still being used and
        critical optimizations are missed. Much faster algorithms
        exist, and the workaround below shows a very powerful
        optimization.

        For a Java implementation and analysis of more efficient
        algorithms, see
        http://www.cis.ksu.edu/~howell/calculator/comparison.html.

        This implementation, using a base 2 or base 10 radix (the
        radix is configurable) can calculate the value in 5 minutes,
        making it approximately 20 times faster than BigInteger. It
        achieves this performance improvement partially by using
        more efficient algorithms for multiplication.

        The current implementation also misses a simple and
        inexpensive optimization when the base is a power of 2
        (which applies in this case:)

        If the base conatins a power of 2, the exponentiation can be
        significantly speeded by factoring out the largest power of
        two (by simply counting trailing zeros in the binary
        expansion, which is easy and fast) as indicated in the
        workaround below. For the case listed above, this performs
        the exponentiation in about .16 seconds or so, a factor of
        tens of thousands of times faster. The code I use to make
        this optimization is listed below.

        Again, this is critical if BigInteger is to be used for
        serious mathematical work.

        Related (but different bugs):
        4641897
        4449911

        STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
        Compile and run the sample code below:

        1. javac BigIntTest.java
        2. java BigIntTest

        (wait over an hour)

        This bug can be reproduced always.

        ---------- BEGIN SOURCE ----------
        import java.math.BigInteger;

        public class BigIntTest
        {
           /** This calculates the largest-known Mersenne Prime, 2^13466917 - 1 */
           public static void main(String[] args)
           {
              int exponent = 13466917;

              System.out.println("Starting");
              BigInteger b = new BigInteger("2");

              BigInteger p;
              p = b.pow(exponent);

              // The shiftLeft() below does the same thing if the base is 2, and in
              // a fraction of a second.
              //p = b.shiftLeft(exponent - 1);

              System.out.println("Exponentiation complete");
              // Note: this takes a long time... over an hour.
           }
        }

        ---------- END SOURCE ----------

        CUSTOMER WORKAROUND :
        One workaround is to use the KSU LargeInteger class used above.

        A missed optimization (that I use before calling pow)
        determines if the base contains a power of 2 and performs
        the shiftLeft optimization, which can be done very fast.)

        This could be done even faster if I had access to the
        internal fields, (without allocation of intermediates) and
        should not be used as the final implementation. It works if
        the base contains a power of 2, and could be easily extended
        to negative bases. It makes my particular application
        hundreds of times faster.

        BigInteger myPow(BigInteger big, int exponent)
        {
           // Note: this can be fixed to work with negative numbers
           if (big.signum() > 0)
           {
              // Get factor of two
              int bit = 0;

              // Count trailing zero bits
              while (big.testBit(bit) == false)
                 bit++;

              // If there's a factor of 2,
              if (bit > 0)
              {
                 // Factor the power of 2 out of the number
                 // (quickly, by shifting right)
                 big = big.shiftRight(bit);

                 // This is the power of 2 we factored out raised
                 // to the specified exponent
                 BigInteger twoPower =
        BigInteger.ONE.shiftLeft(bit*exponent);

                 // If the remainin number is exactly one, we're done
                 if (big.equals(BigInteger.ONE))
                    return twoPower;
                 else
                 {
                    // Raise the remaining part to the exponent
                    big = big.pow(exponent);
                    // multiply by the power of 2
                    return big.multiply(twoPower);
                 }
              }
           }
           
           // If we fell through, do the normal exponent
           return big.pow(exponent);
        }
        (Review ID: 143631)
        ======================================================================
        ###@###.### 2004-11-11 22:25:55 GMT

          Attachments

            Issue Links

              Activity

                People

                Assignee:
                bpb Brian Burkhalter
                Reporter:
                jleesunw Jon Lee (Inactive)
                Votes:
                0 Vote for this issue
                Watchers:
                3 Start watching this issue

                  Dates

                  Created:
                  Updated:
                  Resolved:
                  Imported:
                  Indexed: