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

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



More information about the core-libs-dev mailing list