Details
Description
Name: gm110360 Date: 02/22/2002
FULL PRODUCT VERSION :
java version "1.3.1"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.1b24)
Java HotSpot(TM) Client VM (build 1.3.1b24, 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
currentlyknown 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 largestknown 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)
======================================================================
###@###.### 20041111 22:25:31 GMT
FULL PRODUCT VERSION :
java version "1.3.1"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.1b24)
Java HotSpot(TM) Client VM (build 1.3.1b24, 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
currentlyknown 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 largestknown 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)
======================================================================
###@###.### 20041111 22:25:31 GMT
Attachments
Issue Links
 relates to

JDK4449911 REGRESSION: BigInteger.pow() painfully slow for large exponents (1.3 vs. 1.2.x)
 Closed

JDK4837946 Faster multiplication and exponentiation of large integers
 Closed

JDK8017540 Improve multithreaded contention behavior of BigInteger.toString() radix conversion cache
 Closed

JDK8020641 Clean up some code style in recent BigInteger contributions
 Closed