Review request: Fast multiplication and division (original) (raw)
Tim Buktu tbuktu at hotmail.com
Sat Jan 7 21:10:44 UTC 2012
- Previous message: hg: jdk8/tl/jdk: 7123649: Remove public modifier from Math.powerOfTwoF.
- Next message: Updated unit test for BigInteger patch (#4837946)
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Hi everyone,
I made a patch against the latest BigInteger.java that speeds up multiplication and division of large numbers. It is based on Alan Eliasen's excellent work which unfortunately hasn't been included yet.
There are three algorithms in this patch,
- Karatsuba multiplication which is used above ~480 decimal digits;
- Toom-Cook multiplication which is used above ~720 decimal digits;
- Burnikel-Ziegler division which is used above ~480 decimal digits.
Karatsuba and Toom-Cook were implemented by Alan, and Burnikel-Ziegler was implemented by me. I have reviewed Alan's code, and I verified that the patched BigInteger passes BigIntegerTest (using suitable lengths) as well as my own tests.
On my machine, the speedup for multiplication is as follows:
- 1.3 times faster for 1,000-digit numbers
- 3.9 times faster for 10,000-digit numbers
- 12.4 times faster for 100,000-digit numbers
The speedup for division is as follows:
- 1.4 times faster for 1,000-digit numbers
- 3.4 times faster for 10,000-digit numbers
- 10.4 times faster for 100,000-digit numbers
The patch is at https://gist.github.com/1576016 and the patched BigInteger.java is at https://gist.github.com/1576025 . Thanks,
Tim
- Previous message: hg: jdk8/tl/jdk: 7123649: Remove public modifier from Math.powerOfTwoF.
- Next message: Updated unit test for BigInteger patch (#4837946)
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]