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

[Louis Wasserman]

(https://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means
proves
that the arithmetic mean is >= the geometric mean.)

On Fri, Oct 2, 2015 at 2:16 PM Louis Wasserman <wasserman.louis at gmail.com>
wrote:

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