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

[Louis Wasserman]

Have you investigated Guava's really quite tightly optimized implementation
here?
https://github.com/google/guava/blob/master/guava/src/com/google/common/math/BigIntegerMath.java#L242


A few years back I submitted a patch (now applied) to make
BigInteger.doubleValue() very fast.  If I recall correctly, that patch was
originally inspired by my attempt to optimize sqrt on BigIntegers at the
time.

Converting the BigInteger to a double, using Math.sqrt(double), and using
that as a starting point for Newton's method (converting that floating
point value back to a BigInteger) buys you many bits of precision very
fast.  That result isn't guaranteed to be >= the true result, but one
iteration of Newton's method will fix that.

I'm quite certain you could improve on Guava's implementation even further
with access to MutableBigInteger.

On Fri, Oct 2, 2015 at 1:42 PM Brian Burkhalter <brian.burkhalter at oracle.com>
wrote:

> Please review at your convenience.
>
> Issue:  https://bugs.openjdk.java.net/browse/JDK-8032027
> Patch:  http://cr.openjdk.java.net/~bpb/8032027/webrev.00/
>
> Summary: Add sqrt() and sqrtAndRemainder() methods. The square root
> calculated is the integer square root ’s’ such that for a given integer ’n’
> the value of ’s’ is the largest integer such that s*s <= n. In other words
> it is the floor of the mathematical square root of the value ’n' taken as a
> mathematical real number.
>
> The method of calculation is Newton iteration starting from a value larger
> than the square root which ensures that the convergence is monotonically
> decreasing to the result. An effort is made to make the implementation
> efficient in particular with respect to the amount of memory used. Any
> suggestions as to the improvement of the approach concerning memory use or
> any other aspect of the algorithm would be appreciated, as would be
> suggestions regarding the test.
>
> Thanks,
>
> Brian