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

Tue May 7 09:33:13 UTC 2013

> On May 4, 2013, at 5:13 AM, Alan Eliasen wrote:
>> If you're feeling overwhelmed by the magnitude of the changes to 
>> BigInteger, I would very strongly suggest that you review it in
>> stages. This e-mail proposes stages for the review of this patch.

On 05/06/2013 02:47 PM, Brian Burkhalter wrote:
> It is indeed rather a lot, especially given that the Barrett plus SS
> code alone accounts for more lines of changes than do all the
> previously proposed changes combined.

   I agree that the complexity and volume of code needed to implement
Barrett division and SS multiplication are significantly larger than
Karatsuba and Toom-Cook.

> My rationale for attempting a larger review was that if these new
> changes were not examined now, then they will likely miss the JDK 8
> train altogether. On the other hand if time were to run out on a
> large review then there would be a risk of nothing getting in.

   Yes, I understand that concern, which is why I think a staged review
makes sense.  I've noted before that the leading researcher in Toom-Cook
multiplication, Marco Bodrato, and his colleagues reviewed my Karatsuba
and Toom-Cook patches, and called them "very clean."  This review was
performed to a level of subtlety that they suggested a slighty different
proven-optimal Toom-Cook formulation that came from their research.
This allowed me to remove one shiftLeft from the routine.  This should
give some confidence and reduce review concerns for Karatsuba and
Toom-Cook multiplication.  (Believe me, I've tried to do everything I
can to simplify the review effort!)

   Since first posting these patches, I have had a large number of Java
users contact *me* and use these routines in their JDK.  I know that
these improvements are in good demand and have been widely tested.  I
have used these in very large computational efforts for years, and
tested them against

>> Today, I finished porting my recursive Schoenhage toString
>> routines that I've been using for years in my programming language
>> "Frink" ( http://futureboy.us/frinkdocs/ ).  They are drastically,
>> stunningly faster than the existing BigInteger.toString
>> algorithms.
> 
> The Schoenhage here is unrelated to SS multiplication?

   As you noted later, yes, the routines were both described by (I
believe) the same Schoenhage, but the algorithm has nothing to do with
the Fourier transforms that make up SS multiplication.  The Schoenhage
base conversion is quite simple; it's a recursive divide-and-conquer
that breaks each number approximately in half and then formats each half
separately, which can be done faster.

>> Step 3) would involve faster division:  The Burnickel-Ziegler and 
>> Barrett division routines that Tim wrote.  They are complicated.
> 
> Based on Tim's subsequent comment ("[…] Barrett, especially because
> it is only useful in combination with Schoenhage-Strassen"), it seems
> that Barrett division should be moved to Step 4.

   Yes, that's a good point.  I agree that Barrett division should be
moved to the same timeframe as SS multiplication.  If it makes it more
likely that we get an improved division routine (in Burnickel-Ziegler)
then it's more likely to give a useful combination of features in Java 1.8.

> If this approach were taken, probably we should file three new issues
> for Burnickel-Ziegler division, Schoenhage-Strassen multiplication,
> and Barrett division, respectively. I can take care of this if it
> sounds reasonable.

   That's fine with me.  There are several bugs involved that you can
close after this:

4228681:  Some BigInteger operations are slow with very large numbers
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4228681

   (this was closed but never fixed.)

4837946: Implement Karatsuba multiplication algorithm in BigInteger
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946

4646474: BigInteger.pow() algorithm slow in 1.4.0
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474

   This is improved in many ways:

   * Rewrote pow() to use Karatsuba and Toom-Cook multiplication
   * Implemented Karatsuba squaring
   * Immplemented 3-way Toom-Cook squaring
   * Found good threshholds for Karatsuba and Toom-Cook squaring
   * Added an optimization to use left-shifting for multiples of 2 in
the base.  This improved speed by thousands of times for things like
Mersenne numbers, and may be one of the most significant improvements
for practical programs.

4641897: BigInteger.toString() algorithm slow for large numbers
http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897

> Also helpful to the process would be to have (four) staged patches
> available. I could take on this task as well, i.e., derive patches
> from the code provided thus far, but it might be safer if those more
> intimately familiar with the code helped out, especially as said
> patches might already exist somewhere. 

   Okay, I can provide patches for each of these phases if you'd like.
The patch for the first phase you're looking at (below) would be a good
place to start.

   Do you want these as actual patches?  Or just the whole file that you
can drop into place?  If you prefer patches, what format would you like
them in?

> If I am not mistaken, the
> patch for Step 1 less the pow() improvements is this one:
> https://gist.github.com/tbuktu/1576025. For the time being I will
> start to look at this patch.

   That seems like a good place to start.  It doesn't include the pow()
fixes, though.

>> My latest best version of all of these routines is located at:
>> 
>> http://futureboy.us/temp/BigInteger.java
> 
> This is equivalent to the most recent version of TIm's repository
> 
> https://github.com/tbuktu/bigint
> 
> plus your changes for pow() and toString()?

   Yes, Tim merged my toString changes into his github repository.  The
files there contain all of our known changes.

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