Review Request: BigInteger patch for efficient multiplication and division (#4837946)

[Alan Eliasen]

On 05/07/2013 12:53 PM, Brian Burkhalter wrote:
> To recapitulate in one place, I think we agree on the following sequence:
> 
> Phase 1: Faster multiplication and exponentiation of large integers
> * Karatsuba and Toom-Cook multiplication and squaring; revised pow() function.
> * http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946 (update synopsis/description)
> * http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474
> 
> Phase 2: Faster string conversion of large integers
> * Recursive Schoenhage toString() routines.
> * http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897
> 
> Phase 3: Faster division of large integers
> * Burnickel-Ziegler division routines.
> * Issue to be filed.
> 
> Phase 4: Faster multiplication and division of very large integers
> * Barrett division and Schoenhage-Strassen multiplication.
> * Issue to be filed.

   Okay, I've created a set of patches that implement these 4 phases.
(They're not actually patches, but the entire source file for each
phase, as Brian requested.)

   These are available at:
http://futureboy.us/temp/BigIntegerPatch.zip

   In this zipfile, the file(s) to use for each phase are marked with
the ".phaseX" suffix.  If there is no change in a file for a given
phase, there is no file included for that phase, but you should make
sure that you are still using the BigDecimal and MutableBigInteger
file(s) applied in the previous phases.

   So, to be very clear, the files that make up each phase are:

Phase 1:
   BigInteger.java.phase1
   BigDecimal.java.phase1   (since BigInteger.pow is accelerated, the
workaround in BigDecimal is removed.)

Phase 2:
   BigInteger.java.phase2

Phase 3:
   BigInteger.java.phase3
   MutableBigInteger.java.phase3   (to use Burnikel-Ziegler divide)

Phase 4:
   BigInteger.java.phase4

   For your reference, the final versions of each file are contained
with the ".final" suffix.  These will be identical to previous phases
applied, and you don't have to apply them, but if someone wants to
quickly drop in the best improvements to their own JDK, just use the 3
files with the ".final" suffix.

   Let me know if you have any issues with these.

   Tim and Brian, you might decide amongst yourselves who wants to file
the issues for phases 3 and 4.  I don't know if Brian has any magical
powers to make the issues skip the QA process.

-- 
  Alan Eliasen
  eliasen at mindspring.com
  http://futureboy.us/