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 :
 customer  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  customer .

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) 
======================================================================
  xxxxx@xxxxx   2004-11-11 22:25:55 GMT

N/A

The bug submitter's claims merit investigation.  BigInteger multiplication could use faster algorithms for large numbers
.
  xxxxx@xxxxx   2002-03-05

Will examine this issue as part of Tiger BigInteger and BigDecimal work.

  xxxxx@xxxxx   2002-11-12

Currently deferring until a post-Tiger release.

  xxxxx@xxxxx   2003-10-21

I have written an arbitrary precision mathematics library for 
Java. It's available at: http://www.apfloat.org
When calculating 2^p-1 in radix-10 and converting String, my 
library seems to be about 10 times faster (on Java 1.4.1) 
than the LargeInteger class above.

I filed the original bug report, and note that other VMs
like Kaffe use the GMP libraries for BigInteger work, and
are thousands of times faster than Sun's JVM for large
BigIntegers.  For example, a sample that runs in 16 hours on
Sun's VM will run in about 15 seconds on Kaffe.

Sun needs to look into algorithms that take less than O(n^2)
for multiplication.  As numbers get bigger, the following
multiplication methods are usually used:

* Karatsuba
* Toom-Cook
* FFT

Surely this is a classic example where algorithms and existing code already exist to fix the bug, yet a fix is still pending...? I can understand extensive testing would have to be performed, but 4 years and still waiting for a fix?

I have implemented the karatsuba method of multiplying, and a pow method, which uses this method.
Calculating 2^13466917 takes 63 sec. on a 1.83 GHz Laptop with JDK 1.5_10. 
	public BigInteger powKarat (int exponent)
	{
		if (exponent < 0)
			throw new ArithmeticException ("Negative exponent");
		if (signum == 0)
			return (exponent == 0 ? ONE : this);

		// Perform exponentiation using repeated squaring trick
		int newSign = (signum < 0 && (exponent & 1) == 1 ? -1 : 1);
		
		BigInteger baseToPow2 = this;
		BigInteger result = ONE;

		while (exponent != 0)
		{
			if ((exponent & 1) == 1)
			{
				result = result.karatsuba (baseToPow2);
			}
			if ((exponent >>>= 1) != 0)
			{
				baseToPow2 = baseToPow2. karatsuba (baseToPow2);
			}
		}
		result.signum = newSign;
		
		return result;
	}
	
	
	/**
	 * Returns a BigInteger whose value is <tt>(this * y)</tt> via the Karatsuba Algorithm:<br>
	 * 
	 * If we write this = xL + xH * 2<sup>n</sup>, and y = yL + yH * 2<sup>n</sup>
	 * and precompute:<br>
	 * low    = xL * yL;<br>
     * high   = xH * yH;<br>
     * xy     = (xL + xH) * (yL + yH);<br>
     * middle = xy - low - high;<br>
     * 
     * We can write x*y = low + middle * 2<sup>n</sup> + high * 2<sup>2n</sup>
	 * @param y value to be multiplied by this BigInteger.
	 * @return  <tt>this * y</tt>
	 */
	public BigInteger karatsuba (BigInteger y) 
	{
		if (signum == 0 || y.signum == 0)
			return ZERO;
		
		// switch to normal multiplying when fewer then 1280 bits
		if (mag.length < 40 || y.mag.length < 40) 
        	return multiply (y);
		
        int halfMagLength = Math.max (mag.length, y.mag.length) / 2;

        // x = xL + xH 2^{32*halfMagLength} ,   y = yL + yH 2^{32*halfMagLength}
        BigInteger xH = higherInts (halfMagLength);
        BigInteger xL =  lowerInts (halfMagLength);
        
        BigInteger yH = y. higherInts (halfMagLength);
        BigInteger yL = y.  lowerInts (halfMagLength);

        // compute sub-expressions
        BigInteger low  = xL. karatsuba (yL);
        BigInteger high = xH. karatsuba (yH);
        
        BigInteger xy   = xL. add (xH). karatsuba (yL. add (yH));

        // we can do the following 2 Steps, but we do it with the faster/specialized addShifted routines
//        BigInteger middle = xy. subtract (low). subtract (high). shiftInts (halfMagLength);
//        
//		return low. add (middle). add (high .shiftInts (2*halfMagLength));
        BigInteger middle = xy.  subtract (low). subtract (high);
        
        BigInteger lowMid = low. addShifted (middle, halfMagLength);

		return lowMid. addShifted (high, 2*halfMagLength);
    }


	protected BigInteger lowerInts (int lowerInts)
	{
		int magLen = mag.length;
		
		if (lowerInts >= magLen)
			return this;
		
		int   higherInts = magLen - lowerInts;
		int    newMagLen = lowerInts;
		int [] newMag    = new int [newMagLen];
		
		for (int i = 0; i < newMagLen; i++)
		{
			newMag [i] = mag [i + higherInts];
		}
		
		return new BigInteger (newMag, signum);
	}

	protected BigInteger higherInts (int nInts)
	{
		int    magLen = mag.length;

		if (nInts >= magLen)
			return ZERO;
	
		int newMagLen = magLen - nInts;
		int [] newMag = new int [newMagLen];
		
		for (int i = 0; i < newMagLen; i++)
		{
			newMag [i] = mag [i];
		}
		
		return new BigInteger (newMag, signum);
	}

	protected BigInteger shiftInts (int nInts)
	{
		int    magLen = mag.length;
		int newMagLen = magLen + nInts;
		
		int [] newMag = new int [newMagLen];
		
		for (int i = 0; i < magLen; i++)
		{
			newMag [i] = mag [i];
		}
		
		return new BigInteger (newMag, signum);
	}