RFR of 8032027: Add BigInteger square root methods
lowasser at google.com
Fri Oct 2 21:18:22 UTC 2015
that the arithmetic mean is >= the geometric mean.)
On Fri, Oct 2, 2015 at 2:16 PM Louis Wasserman <wasserman.louis at gmail.com>
> 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
> 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
>> 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.
>> 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?
>> > 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
>> > 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