Faster string conversion of large integers

Name: gm110360 Date: 02/22/2002


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 :
Microsoft 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 III. (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)
======================================================================
###@###.### 2004-11-11 22:25:31 GMT