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

[Brian Burkhalter]

Alan,

On May 7, 2013, at 2:33 AM, Alan Eliasen wrote:

>> 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.

Agreed.

> 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.

Definitely. I cannot by any stretch purport to being a domain expert at that level. My role is simply to apply due diligence in shepherding these improvements through final review, testing, and integration insofar as possible.

> (Believe me, I've tried to do everything I
> can to simplify the review effort!)

I can see that.

>   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 [sic]

The demand and utility are clear which is why this is at the top of the list now.

>>> 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.

That was the idea.

>> 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.)

It is marked "Resolved-Fixed" even though it is not but I am not sure it is worth re-opening it and re-marking it as resolved. I think it can be linked however to the following issue with an accompanying comment.

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

Assuming that such modification of an existing issue is acceptable, this one ought to be renamed to something like "Implement Karatsuba and Toom-Cook multiplication and squaring" with an appropriate update to the description.

>> 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.

That would be very helpful and appreciated. Please see the summary at the end.

> The patch for the first phase you're looking at (below) would be a good
> place to start.

As caught by Tim and myself, that patch is not really equivalent to the Phase 1 patch.

>   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?

Whole files are preferable; I can generate the diffs myself.

>> 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.

And as noted elsewhere does include Burnickel-Ziegler so it is not apropos for Phase 1.

>>> 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.

Good to know.

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.

Thanks again for your comments and assistance.

Brian