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

[Brian Burkhalter]

I am aware of the classes at

http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/math/BigIntegerMath.html

but have not looked at anything beyond the javadoc specification primarily in the interest of licensing purity. Perhaps that is not a problem but I preferred to stay clear of it for now.

The implementation I have here is effectively the one from Hacker’s Delight (2nd ed.). The initial guess is intended to be larger than the true result in order to simplify the termination condition of that algorithm as the monotonic convergence cannot have any oscillation between potential terminal values.

There is certainly some room here for improvement in the range of input values less than Double.MAX_VALUE but this is a first stab at the implementation so hopefully such improvement may be brought in later if it is not in the first pass.

Thanks,

Brian

On Oct 2, 2015, at 1:54 PM, Louis Wasserman <lowasser at google.com> wrote:

> 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.