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

[joe darcy]

On 10/3/2015 2:38 AM, Andrew Haley wrote:
> On 02/10/15 21:41, Brian Burkhalter wrote:
>
>> Any suggestions as to the improvement of the approach concerning
>> memory use or any other aspect of the algorithm would be
>> appreciated, as would be suggestions regarding the test.
> This algorithm doesn't look like the best to me because it's got this
> slow division in the middle.  If we calculate 1/sqrt(x) instead we can
> use a version of Newton's iteration which requires no division.
>
> Starting with an approximation y = 1/sqrt(x) using the first few digits,
>
>       y = y * (3 - x*y^2)
>           ---------------
>                  2
>
> ... and fix it all up with a single iteration of Heron's algorithm at the
> end.
>
> But even better is Karatsuba Square Root:
> https://hal.inria.fr/inria-00072854/document
>
> I guess it all depends on how much work we think this deserves.  In
> general the core algorithms in BigInteger are among the best, and it
> would be nice to continue this tradition.

For an initial implementation, I think it is acceptable to use a simple 
algorithm that is clearly correct. That algorithm can then be replaced 
with faster ones once adequate tests are built up (with the original 
implementation perhaps retiring to the regression tests area where it 
can be used for comparison purposes).

-Joe