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

Alan Eliasen eliasen at mindspring.com
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:

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/

More information about the core-libs-dev mailing list