Details
Description
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.
ToomCook 3way multiplication is also a recursive algorithm for multiplying multiprecision 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/toomcook/ http://bodrato.it/papers/#WAIFI2007.
Exponentiation may be improved by factoring out powers of two for leftshifting, and using Karatsuba and ToomCook squaring for large numbers.
###@###.### 20030326
Attachments
Issue Links
 duplicates

JDK4646474 BigInteger.pow() algorithm slow in 1.4.0
 Closed
 relates to

JDK8031960 Improve BigInteger Karatsuba multiplication performance under high allocation pressure
 Open

JDK8020641 Clean up some code style in recent BigInteger contributions
 Closed

JDK6471906 java.lang.NegativeArraySizeException in tenToThe
 Closed

JDK8014320 Faster multiplication and division of very large integers
 Open

JDK8014319 Faster division of large integers
 Closed

JDK4641897 Faster string conversion of large integers
 Closed