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
