JDK-4449911 : REGRESSION: BigInteger.pow() painfully slow for large exponents (1.3 vs. 1.2.x)
  • Type: Bug
  • Component: core-libs
  • Sub-Component: java.math
  • Affected Version: 1.3.0
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2001-04-24
  • Updated: 2001-10-12
  • Resolved: 2001-07-27
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
1.4.0 beta2Fixed
Related Reports
Relates :  
Relates :  

Name: krC82822			Date: 04/24/2001

24 Apr 2001, eval1127@eng -- 1.3.x/1.4.x significantly slower
than 1.2.x.  See Comments section.
java version "1.3.0_02"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.3.0_02)
Java HotSpot(TM) Client VM (build 1.3.0_02, mixed mode)

Sample program:

import java.math.*;

public class powtest
    public static void main(String[] args)
        long t1 = System.currentTimeMillis();

        BigInteger result = BigInteger.valueOf(10).pow(65536);

        System.out.println("runtime:       " +
           (System.currentTimeMillis()-t1)/1000.0 + " secs");

System is: W2K Server SP1 AMD 550MHz

Running against JDK 1.3.0_02 it takes about 65 seconds. If running against JDK
1.2.2_006 it takes 0.5 seconds. Someone seems to have badly "over-optimized"
this ...

(Review ID: 123144) 

CONVERTED DATA BugTraq+ Release Management Values COMMIT TO FIX: merlin-beta2 FIXED IN: merlin-beta2 INTEGRATED IN: merlin-beta2 VERIFIED IN: merlin-beta3

EVALUATION Confirmed existence of slowdown in 1.4. Going from 1.2 -> 1.3+, BigInteger went from calls to a native C library to all Java. For both, both the Java+C version and the all Java version using the same "Russian peasant" algorithm. However, in the Java version, the multiplications and squaring operations have been partially inlined manually. This partial inlining omitted a step which removes extra zeros from intermediate results. When raising large numbers to small exponents, this omission leads to faster code; unfortunately, when raising small numbers to large exponents, it leads to the large slowdown observed in this bug. The obvious fix is to restore the zero removal to intermediate results; this will give correct answers, albeit somewhat more slowly in certain cases. A more sophisticated change would try to determine the conditions when the zero removal would be profitable. However, there is unlikely to be time for that engineering work by Merlin FCS. I will make the obvious change discused above and verify correctness and lack of (different) horrible performance degradations before doing the putback. joe.darcy@eng 2001-07-17 Putback changes discussed above -- BigInteger regression tests passed and actually ran faster. joe.darcy@eng 2001-07-23