[9] RFR of 8032027: Add BigInteger square root methods

[joe darcy]

Returning to this review...

On 10/7/2015 7:02 PM, Brian Burkhalter wrote:
> Joe / Andrew / Louis,
>
> Following up on the thread regarding https://bugs.openjdk.java.net/browse/JDK-8032027.
>
> I revised the algorithm similarly to what Louis suggested for the initial value of the iteration. I also tightened up the memory usage. The updated version is here:
>
> http://cr.openjdk.java.net/~bpb/8032027/webrev.01/
>
> I did not at this time change the algorithm to compute the reciprocal of the square root instead of the root directly as Andrew suggested. Apparently this would improve the rate of convergence from quadratic to cubic, but I am inclined to file this and the Karatsuba square root as two separate issues for future enhancement.
>
> Likewise I did not yet include the special case which Joe mentioned for tuning performance for n < 2^1023 wherein the spread of unity bits is sufficiently small. If this does not make it into the current round of revisions a separate enhancement issue may likewise be filed.
>
> Thanks,
>
> Brian

A few comments and suggestions:

2452     public BigInteger[] sqrtAndRemainder() {
2453         BigInteger s = sqrt();
2454         BigInteger r = this.subtract(s.square());
2455         return new BigInteger[] {s, r};
2456     }

It that "remainder >= 0" would be a good assert to add before line 2455.

As a stylistic matter, in MutableBigInteger I would prefer a direct 
check of bitLength rather than relying on the exception being thrown 
from longValueExact. Something like

if (bitLength < 63)
    // use double initial approx
else
   // use other technique

In the tests, use of lambda could allow the core testing logic to be shared.

Thanks,

-Joe