JDK-4837946 : Faster multiplication and exponentiation of large integers
  • Type: Enhancement
  • Component: core-libs
  • Sub-Component: java.math
  • Affected Version: 5.0
  • Priority: P3
  • Status: Closed
  • Resolution: Fixed
  • OS: generic
  • CPU: generic
  • Submitted: 2003-03-26
  • Updated: 2014-01-16
  • Resolved: 2013-06-19
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.
8 b96Fixed
Related Reports
Duplicate :  
Relates :  
Relates :  
Relates :  
Relates :  
Relates :  
Relates :  
Implement Karatsuba and 3-way Toom-Cook multiplication of large integers, and improve exponentiation algorithm used in pow().

Karatsuba is a recursive algorithm for multiplying multi precision integers. It has a running time of O(n ^ 1.58) compared to O(n ^ 2) [or O(n * m)] for the "simple" multiplication algorithm. It is discussed in Knuth volume 2 and http://cr.yp.to/papers/m3.pdf as well as other literature.

Anecdotal evidence indicates that Karatsuba is the best multiplication algorithm for numbers of around 500 to a few 1000 bits as are commonly used in cryptographic and other common applications. Therefore, we should consider implementing it in BigInteger.

Toom-Cook 3-way multiplication is also a recursive algorithm for multiplying multi-precision integers that becomes more effective than Karatsuba for integers beyond a larger threshold of number of bits. More information may be obtained here: http://bodrato.it/toom-cook/ http://bodrato.it/papers/#WAIFI2007.

Exponentiation may be improved by factoring out powers of two for left-shifting, and using Karatsuba and Toom-Cook squaring for large numbers.

###@###.### 2003-03-26

See http://mail.openjdk.java.net/pipermail/core-libs-dev/2012-December/013324.html.

CONVERTED DATA BugTraq+ Release Management Values COMMIT TO FIX: dragon

EVALUATION Using more efficient and sophisticated algorithms to implement BigInteger operations is a venerable goal. ###@###.### 2003-03-26 Currently deferring until a post-Tiger release. ###@###.### 2003-10-21