Square Root of a BigInteger

[Aaron Rustad]

How do you do a Square Root on a BigInteger object?

--

----------------------
Aaron Rustad
Critical Mass

(403) 262 3006 ext. 2206
aar...@criticalmass.com
66310773 (ICQ)

[Patricia Shanahan]

What type should the output be?

[refactor]

> In article <8jdkgr$q1r$1...@cleavage.canuck.com>,

> "Aaron Rustad" <aar...@criticalmass.com> wrote:
> How do you do a Square Root on a BigInteger object?

Write your own, assuming you want a BigInteger with complete precision
as a result.

See this URL: Recursive Algorithms: Square Root
128.252.165.3/~kjg/cs101/Notes/SquareRoot/sqrt.html
It starts out: Suppose Java did not provide a square root procedure.
Could we build one ourselves?

The code given uses doubles. It can be converted to BigInteger and,
with tweak on the division step, will achieve the desired result.

Assuming that one wants a BigInteger result, a starting approximation
is to convert the BigInteger to a double, take the square root of that,
convert the result back to a BigInteger (probably via use of
DecimalFormat with grouping set to 0). A double only has about 16
digits of precision. The result would be accurate for roughly a 32
digit or less BigInteger. A BigInteger with more digits could then use
that approximation as a starting point in a BigInteger code version of
what is suggested in that URL.

Using that double as a seed can reduce significantly on the number of
iterations required.

Another issue is does one want the BigInteger whose square is below or
equal, or does one want the one that is above or equal? Or the one
with the least error?

Example: 9,995,082 has a square root of 3161.499960 --
do you want 3161 or 3162 as the correct answer
realizing that one doesn't have access to the
fractional part in the BigInteger algorithm.

The alogorithm may converge on one or the other
depending on the starting seed.

H.

Sent via Deja.com http://www.deja.com/
Before you buy.

[Patricia Shanahan]

refactor wrote:
>
> > In article <8jdkgr$q1r$1...@cleavage.canuck.com>,
> > "Aaron Rustad" <aar...@criticalmass.com> wrote:
> > How do you do a Square Root on a BigInteger object?
>
> Write your own, assuming you want a BigInteger with complete precision
> as a result.
>
> See this URL: Recursive Algorithms: Square Root
> 128.252.165.3/~kjg/cs101/Notes/SquareRoot/sqrt.html
> It starts out: Suppose Java did not provide a square root procedure.
> Could we build one ourselves?
>
> The code given uses doubles. It can be converted to BigInteger and,
> with tweak on the division step, will achieve the desired result.
>
> Assuming that one wants a BigInteger result, a starting approximation
> is to convert the BigInteger to a double, take the square root of that,
> convert the result back to a BigInteger (probably via use of
> DecimalFormat with grouping set to 0). A double only has about 16
> digits of precision. The result would be accurate for roughly a 32
> digit or less BigInteger. A BigInteger with more digits could then use
> that approximation as a starting point in a BigInteger code version of
> what is suggested in that URL.

One caveat here. If there is a possibility that the input has 308 or
more digits you need to allow for getting an infinite result on the
conversion to double, requiring some pre-scaling.

>
> Using that double as a seed can reduce significantly on the number of
> iterations required.
>
> Another issue is does one want the BigInteger whose square is below or
> equal, or does one want the one that is above or equal? Or the one
> with the least error?

Yup - I've been trying to get clarification on just what result is
needed for non-integer results, in order to know whether e.g. BigDecimal
should be used to get extra digits for rounding.

[refactor]

Good point. Too many digits would mean that a double would be useless
for directly determining the seed.

One could check that bigInteger.doubleValeue() didn't yield a
POSITIVE_INFINITY. If it did, and one still wanted to seed the
starting guess with something better than one, then a seed could be
created using a BigInteger("0") that has had a setBit method call to
turn on the bit at the original values bitLength()/2. That gets one in
the ball park. The number of iterations in my test cases were six at
max using this technique. Not as good as when one can use the
doubleValue as the seed, but close enough.

Starting with a seed one will take a number of iterations that is
slightly larger than half the value of bigInteger.bitLength().

Depending on the requirements, as you say, BigDecimal might be useful.

One wonders for what problem is having a Square Root of a BigInteger a
solution.

[Patricia Shanahan]

Alternatively, prescale the BigInteger. If you have input N, and
determine the square root of N/(x**2) for some convenient x, then
multiplying that square root by x will yield a good starting point.