18 views

Skip to first unread message

Jun 28, 2000, 3:00:00 AM6/28/00

to

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)

Jun 28, 2000, 3:00:00 AM6/28/00

to

What type should the output be?

Jun 29, 2000, 3:00:00 AM6/29/00

to

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

Jun 29, 2000, 3:00:00 AM6/29/00

to

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.

Jun 30, 2000, 3:00:00 AM6/30/00

to

Good point. Too many digits would mean that a double would be useless

for directly determining the seed.

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.

Jun 30, 2000, 3:00:00 AM6/30/00

to

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.

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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu