[9] RFR of 8032027: Add BigInteger square root methods (original) (raw)

Louis Wasserman wasserman.louis at gmail.com
Fri Oct 2 21:16:32 UTC 2015

I'm pretty sure we could potentially public-domain our implementation, if that were an issue.

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.

This isn't a problem. The arithmetic mean of any two nonnegative numbers is always greater than their geometric mean, so for any nonnegative a, (a + x/a)/2 >= sqrt(a * x/a) = sqrt(x). So once you do one Newton iteration, the convergence is guaranteed to be monotonically decreasing after that point.

Newton's method doubles the number of correct digits with every iteration. So you're paying one extra Newton iteration, but in exchange you're getting -handwave- 50 correct bits to start out with. That more than pays for itself.

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.

It doesn't matter whether the input is bigger than Double.MAX_VALUE. You can just find some even number, s, such that x.shiftRight(s) < 2^52. Then use

doubleToBigInteger(Math.sqrt(x.shiftRight(s))).shiftLeft(s / 2)

as your starting estimate. You're still getting ~50 correct bits to start your Newton iteration.

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

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

More information about the core-libs-dev mailing list