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

Tim Buktu tbuktu at hotmail.com
Sun May 5 02:48:39 UTC 2013

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

More information about the core-libs-dev mailing list