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

[Brian Burkhalter]

Hi Alan,

Thank you for the detailed, thoughtful message.

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.

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.

>   Since I first posted these patches over 5 years ago, we were asked to
> make patches as small as possible so they would get reviewed more
> quickly.

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.

> That's why my patches focused on what was a minimal but
> necessary subset: making multiply and pow work *much* faster with very
> simple, understandable, well-known, hard-to-get-wrong routines and
> simple optimizations that built on existing routines but gave very
> significant performance increases.  (Implementing Karatsuba and
> Toom-Cook multiplication routines in Java is often given as a homework
> problem in undergrad Algorithms courses.  Understanding their
> correctness requires nothing more than first-year Algebra.)

Apparently - and fortunately - algebra as in pre-calculus not as in abstract (groups / rings / fields): something which I studied as an undergraduate but which has long since succumbed to brain rot.

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

>   I can personally vouch for having very strongly tested the parts of
> multiplication and pow that I wrote, which include:
> 
>   * Karatsuba multiplication
>   * 3-way Toom-Cook multiplication
>   * Karatsuba squaring
>   * Toom-Cook squaring
>   * Revised pow() function

That is good to know.

>   While I have been using Tim's Schönhage-Strassen multiplication and
> Burnickel-Ziegler division routines in my daily work, and have not
> detected failures, I have not written explicit tests for division at
> all, and my number of very large integer divisions has been small.  I
> have implicitly used his division routines in my base conversion
> routines for large numbers, and have found no errors.

It looks like Tim has made some changes to BigIntegerTest which exercise the Burnickel-Ziegler code.

>   Brian, would it be possible to make BigInteger.square() public?

I am looking into it.

>   If reviewing time is limited, I might suggest performing the reviews
> and integration in a few steps:
> 
>   Step 1) would be integrating the simple, high-benefit, low-risk
> changes that I made:
> 
>   * Karatsuba multiplication
>   * 3-way Toom-Cook multiplication
>   * Karatsuba squaring
>   * Toom-Cook squaring
>   * Revised pow() function

This is equivalent to http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946 plus http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474.

>   Step 2) incorporating my toString changes.  It's useless to work with
> these very big numbers if you can't output them in reasonable time. The bug for improving toString is:
> 
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897
> 
>   My complete patch contains very much faster, simple Schoenhage
> recursive base conversion routines for toString.

This and quick look at your code answers my question, i.e., it is unrelated to SS multiplication.

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

>   Step 4) integrating what I believe are the most tricky
> routines:  Schoenhage-Strassen (SS) multiplication.  This stuff is hard.

I think that your proposal for a staged review is a good plan including in terms of the order in which the algorithms would be addressed. I would like to know what others think about it.

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.

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

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

Thanks,

Brian