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

[Brian Burkhalter]

Hello,

We are at long last soon to commence our long overdue effort to integrate this important submission.

To this end I have a couple of questions and a comment below.

Thanks,

Brian

On Mar 10, 2013, at 1:39 PM, Tim Buktu wrote:

> I have updated the patch. It now contains Alan Eliasen's fast square() and pow() implementations.
> Special characters have been replaced with ASCII ones.
> 
> Also included is a patched MutableBigInteger which uses the fast division algorithm in BigInteger, and a patched BigDecimal which uses the fast BigInteger.pow() method. Both changes speed up BigDecimal division.
> BigDecimal division is still much slower than BigInteger division (except BigDecimal.divideAndRound) because it calls doRound(), setScale(), and bigMultiplyPowerTen() which are pretty slow. Maybe these
> methods can be made more efficient.
> 
> To view the four patched files (#4 is BigIntegerTest.java) on one page, go to
> 
> https://gist.github.com/tbuktu/1576025 ,
> 
> or get them individually at
> 
> https://gist.github.com/tbuktu/1576025/raw/96e9dfd9261862223aa9ff81618f1d85045e85a5/BigInteger.java
> https://gist.github.com/tbuktu/1576025/raw/447db955ef74b065b03b0b45abd443cea5d7b2c6/MutableBigInteger.java
> https://gist.github.com/tbuktu/1576025/raw/6863a38032835b48b73cbce5aa833680c881557f/BigDecimal.java
> https://gist.github.com/tbuktu/1576025/raw/11977be7d001e093baa915b4370f326e30218eec/BigIntegerTest.java

This patch differs from the code in https://github.com/tbuktu/bigint.git. Notably I observed that Schonhage-Strassen multiplication and Barrett division are not present. Is this intentional and if so why would that be? Are the implementations of these additional algorithms not quite ready for contribution or is there a licensing issue perhaps?

> Semi-related: I think there is a bug in
> jdk/test/java/math/BigInteger/CompareToTests.java and
> jdk/test/java/math/BigDecimal/CompareToTests.java. It prints failures
> (with or without my patches) but the overall test doesn't fail.

I have taken note of this with the intent of investigating it in the course of evaluating this submission.