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

Brian Burkhalter brian.burkhalter at oracle.com
Tue May 7 18:53:39 UTC 2013

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/viewbug.do?bugid=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/viewbug.do?bugid=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

Phase 2: Faster string conversion of large integers

Phase 3: Faster division of large integers

Phase 4: Faster multiplication and division of very large integers

Thanks again for your comments and assistance.

Brian

More information about the core-libs-dev mailing list