[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