[PATCH] 4837946: Implement Karatsuba multiplication algorithm in BigInteger

Alan Eliasen eliasen at mindspring.com
Wed Feb 20 22:50:58 UTC 2008


 Attached is a *revised* patch for bug 4837946, for implementing
asymptotically
faster algorithms for multiplication of large numbers in the BigInteger
class:

 http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

   It only differs from my patch posted yesterday in one respect--the
new methods getLower() and getUpper() now call
trustedStripLeadingZeroInts() which has two effects:

   * Helps preserve the invariant expected by BigInteger that zero has a
signum of zero and a mag array with length of zero (due to the way that
the private constructor BigInteger(int[] mag, int signum) works.)

   * Optimizes some cases like multiplying 2*1000000, where the bit
string has a large number of zeroes in a row.

   Please use this patch instead of the one I posted yesterday.

-- 
  Alan Eliasen              |  "Furious activity is no substitute
  eliasen at mindspring.com    |    for understanding."
  http://futureboy.us/      |           --H.H. Williams
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: BigInteger.diff
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20080220/868f413c/BigInteger.diff>


More information about the core-libs-dev mailing list