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

[Tim Buktu]

On 05/04/2013 2:13 PM, Alan Eliasen wrote:
>    My multiplication tests were written to test general multiplication,
> but also to very strongly test around the regions at which Karatsuba and
> Toom-Cook have edge cases.  Since I don't know the Schönhage-Strassen
> algorithms, I don't know where they might have particular edge cases, so
> I haven't written any specific tests for them.
Edge cases in SS are powers of two and powers of two plus one. I added
code to (the patched) BigIntegerTest.java earlier that tests those numbers.
According to the author of the SS implementation in GMP, numbers with
long sequences of zeros or ones are good test cases as well. Those have
been in my patched BigIntegerTest.java for a while.

BigIntegerTest only does so many iterations of course. I increased that
number so it would run for about a day, and the tests all passed. I did
some optimizations after that which caused a couple of bugs, but they
have been fixed and BigIntegerTest hasn't failed since (including
another 24h run).
I will run the latest version of BigIntegerTest (which tests the above
mentioned numbers around powers of two) for a day or so and report back.

>    Step 3) would involve faster division:  The Burnickel-Ziegler and
> Barrett division routines that Tim wrote.  These are important for
> making base conversion faster, and making division reasonably fast.
> (For many programs, division speed is the limiting factor.  This limits
> the performance of BigDecimal too.)  They are complicated.
I agree on Barrett, especially because it is only useful in combination
with Schoenhage-Strassen. Burnikel-Ziegler on the other hand, covers a
wide range (750 - 750,000 digits, comparable to Toom-Cook) and it's not
nearly as complex as SS.

Tim