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

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

ADDITIONAL OPERATING SYSTEMS :
All


A DESCRIPTION OF THE PROBLEM :
The algorithm for radix conversion in BigInteger.toString()
is very inefficient for large numbers, making it unusable
for serious mathematical work.

For example, calculating the value of the largest
currently-known Mersenne prime, 2^13466917 - 1, takes about
.16 seconds on an 800 MHz Pentium  customer .  (This is if you work
around the similar critical slowness in pow(), see bug
4449911 )  No big problem in the exponentiation (but there
would be if it was a base that wasn't a power of 2.)

But if you want to see the results, toString() takes over 14
*hours*.  Other tools, such as Mathematica, return the value
in a few seconds.

The algorithm used is inefficient; much more efficient
algorithms exist.  See the recursive decomposition
algorithms attributed to Knuth and Schoenhage in Donald
Knuth, The Art of Computer Programming, Vol. 2:
Seminumerical Algorithms, in the section "Answers to
Exercises, Section 4.4"  Section 4.4 of the text (which
resembles the algorithms used in BigInteger) are orders of
magnitude slower than the algorithms outlined in the
"Answers to Exercises."

All algorithms will also benefit from improving the
quadratic behavior of the multiply, divide, and
exponentiation functions as implemented.

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

This implementation, using a base 10 radix (the radix is
configurable) can calculate and print the value in about 6
minutes, making it a minimum of 140 times faster.  Almost
all of this time is in the exponentiation (which is of
course harder to do in base 10, but still much faster than
the JDK 1.3.1 implementation of pow())

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

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

javac BigIntTest.java
java BigIntTest

(wait 14 hours...)



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)
   {
      System.out.println("Starting");
      BigInteger b = new BigInteger("2");

      // The shiftLeft below is a kludge to get around how slow pow() is in 1.3)
      // Internally, pow() should be implemented so that it does this
      // shiftLeft optimization for bases that are powers of 2.
      BigInteger p = b.shiftLeft(13466917 - 1);
      System.out.println("Exponentiation complete");
      p = p.subtract(new BigInteger("1"));
      System.out.println("Subtraction complete");

      // Now wait about a day for the toString() to work.
      System.out.println(p.toString());
   }
}
---------- END SOURCE ----------

CUSTOMER WORKAROUND :
Use Mathematica or the LargeInteger class mentioned above.
(Review ID: 143124) 
======================================================================
  xxxxx@xxxxx   2004-11-11 22:25:31 GMT

N/A

The pow performance problem referenced in bug 4449911 has been fixed in Merlin.

Will investigate reported performance issue of BigDecimal toString conversion for large numbers; citing relevant references appreciated.

  xxxxx@xxxxx   2002-02-25

Will investiate as part of Tiger BigInteger and BigDecimal work.

  xxxxx@xxxxx   2002-11-12

Currently deferring to a post-Tiger release.

  xxxxx@xxxxx   2003-10-21

Thanks for the acceptance of the bug.  I do have to disagree
 with the analysis that pow() doesn't have a significant
performance problem... (although it is faster than the
admittedly broken version distributed with 1.3)  

It still takes 6242 seconds (104 minutes) to execute
2^13466917 in JDK 1.4.0 (on an 800 MHz Pentium III),
compared to 306 seconds with the KSU LargeInteger class
(working with a radix of 2 or 10) noted above, making the
KSU class 85 times faster, even when using a radix which
does not lend itself well to calculating powers of 2.

   Note that the shiftLeft optimization used above (which
can be used whenver the base is a power of 2) performs the
exponentiation in around .16 seconds or less (that's about
the size of a clock tick on my system.)

  I will file the problem with pow() as a separate RFE.

Would it be worthwhile putting some specific performance
optimizations in the Big{Decimal,Integer} classes? For
instance, if the value is 2, and the pow() method is called
with an integer value, this can internally be reduced to a
shift.

I have a sample of the shiftLeft() optimization which can be
used whenever the base contains a power of 2 in bug 4646474.
 This provides incredible speedups in some cases and is very
simple, so it should definitely be used when applicable.

The person making the evaluation about the pow performance
problem should also read bug 4646474, which discusses that
although that regression was fixed, a highly-non-optimal
algorithm is still being used for pow() and other
implementations in Java do it much, much faster.

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.

But How to convert String back to Big Integer