square roots of big integers

Thread view:

Jeremy Watts - 20 Jul 2004 18:26 GMT

hi,

i know about javas 'big integer' for handling of large integers, but
wondered whether it can find square roots of large numbers also?

Reply to this Message

Andrew Thompson - 20 Jul 2004 17:41 GMT

> i know about javas 'big integer' for handling of large integers, but
> wondered whether it can find square roots of large numbers also?

I'll give you two guesses,
<http://java.sun.com/j2se/1.4.2/docs/api/java/math/package-summary.html>
..and the first one doesn't count. ;-)

Signature

Andrew Thompson
http://www.PhySci.org/ Open-source software suite
http://www.PhySci.org/codes/ Web & IT Help
http://www.1point1C.org/ Science & Technology

Reply to this Message

Ian Shef - 20 Jul 2004 20:21 GMT

>> i know about javas 'big integer' for handling of large integers, but
>> wondered whether it can find square roots of large numbers also?
>
> I'll give you two guesses,
> <http://java.sun.com/j2se/1.4.2/docs/api/java/math/package-summary.html>
> ..and the first one doesn't count. ;-)

but BigInteger does support add, subtract, multiply, and divide, so I suppose
that a Newton-Raphson iteration or other method could be implemented.

Signature

Ian Shef
These are my personal opinions and not those of my employer.

Reply to this Message

Lāʻie Techie - 28 Jul 2004 07:28 GMT

> but BigInteger does support add, subtract, multiply, and divide, so I
> suppose that a Newton-Raphson iteration or other method could be
> implemented.

The problem is that not all integers have a root that is also an integer.
Any algorithm for finding roots should be in the BigDecimal class.

HTH,
La'ie Techie

Reply to this Message

Ian Shef - 28 Jul 2004 20:11 GMT

=?UTF-8?b?TMSByrtpZSBUZWNoaWU=?= <laie@win_remove_get_nospam_solutions.com>
wrote in news:pan.2004.07.28.06.28.33.460506
@win_remove_get_nospam_solutions.com:

>> but BigInteger does support add, subtract, multiply, and divide, so I
>> suppose that a Newton-Raphson iteration or other method could be
>> implemented.
>
> The problem is that not all integers have a root that is also an integer.
> Any algorithm for finding roots should be in the BigDecimal class.

My (possibly false) assumption was that if someone was looking for a
BigInteger square root of a BitInteger, then they understood that the answer
would be an approximation.

I agree that using BigDecimal will provide an exact answer for more cases
than would BigInteger. However, there will always be cases (e.g. square root
of 2) where the result will remain an approximation. It is a question of how
close the answer needs to be.

It is too bad that square root was not provided in BigInteger and in
BigDecimal. Even better, how about ALL of the functions of java.lang.math ?

Signature

Ian Shef
These are my personal opinions and not those of my employer.

Reply to this Message

Michael Amling - 29 Jul 2004 00:46 GMT

> =?UTF-8?b?TMSByrtpZSBUZWNoaWU=?= <laie@win_remove_get_nospam_solutions.com>
> wrote in news:pan.2004.07.28.06.28.33.460506
[quoted text clipped - 13 lines]
> I agree that using BigDecimal will provide an exact answer for more cases
> than would BigInteger.

If the square root of an integer is not itself an integer then the
exact answer can't be represented by BigDecimal.

> However, there will always be cases (e.g. square root
> of 2) where the result will remain an approximation. It is a question of how
> close the answer needs to be.
>
> It is too bad that square root was not provided in BigInteger and in
> BigDecimal. Even better, how about ALL of the functions of java.lang.math ?

--Mike Amling

Reply to this Message

Roedy Green - 20 Jul 2004 21:26 GMT

>i know about javas 'big integer' for handling of large integers, but
>wondered whether it can find square roots of large numbers also?

I'd think you could come up with a homing procedure that might work
something like this:

guess = v / 2;

alt = v / guess;

newguess = ( guess + alt ) / 2;

You could do these operations with BigInteger.

Signature

Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Reply to this Message

Ian Shef - 21 Jul 2004 19:43 GMT

>>i know about javas 'big integer' for handling of large integers, but
>>wondered whether it can find square roots of large numbers also?
[quoted text clipped - 9 lines]
>
> You could do these operations with BigInteger.

Here is Newton-Raphson from
http://www.laynetworks.com/Numerical%20and%20Statistical%20Computing_2.htm
for the square root of 25:

[It looks better on the web page. x^2 means x squared. xn means "x sub
n". xn+1 means "x sub (n+1)".

let x=square root of 25
so that x2-25=0
taking f(x)=x^2-25 , newton raphson method gives
xn+1 = xn - [ f(xn) /f ?(xn) ]
=xn - [ (xn)^2 - 25 /2xn ]
= [ xn + (25 / xn ) ] / 2

So

xn+1 = [ xn + (25 / xn ) ] / 2

which I think is the same as the proposal by Jeremy Watts (where Jeremy
proposes that x0 = 25/2). Jeremy, you just re-invented Newton-Raphson!
This require only addition and division, so it can be handled by
BigInteger.

Signature

Ian Shef
These are my personal opinions and not those of my employer.

Reply to this Message

Ian Shef - 21 Jul 2004 19:47 GMT

>>>i know about javas 'big integer' for handling of large integers, but
>>>wondered whether it can find square roots of large numbers also?
[quoted text clipped - 32 lines]
> This require only addition and division, so it can be handled by
> BigInteger.

... and to follow up on my own post:

In general, Newton-Raphson doubles the number of correct bits at each
iteration, so it does not require a lot of iterations to get a good result.
Using BigInteger, the divisions will be have results truncated to a
BigInteger, so perhaps you do not quite get a doubling of correct bits on
each iteration, but you should still get rapid results.

Signature

Ian Shef
These are my personal opinions and not those of my employer.

Reply to this Message

Roedy Green - 21 Jul 2004 20:23 GMT

>xn+1 = [ xn + (25 / xn ) ] / 2
>
>which I think is the same as the proposal by Jeremy Watts

that is also my algorithm. I just did mine heuristically. It is just
a fluke it came out the same as Newton.

Signature

Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Reply to this Message

Boudewijn Dijkstra - 01 Aug 2004 22:25 GMT

> >i know about javas 'big integer' for handling of large integers, but
> >wondered whether it can find square roots of large numbers also?
[quoted text clipped - 3 lines]
>
> guess = v / 2;

Wouldn't

guess = Math.sqrt(doubleValue());

be a more desirable first guess?

> alt = v / guess;
>
> newguess = ( guess + alt ) / 2;
>
> You could do these operations with BigInteger.

Reply to this Message

Roedy Green - 01 Aug 2004 23:26 GMT

>Wouldn't
>
> guess = Math.sqrt(doubleValue());
>
>be a more desirable first guess?

it would be if the BigInteger were in range. Many of the BigIntegers
I play with are about 1000 bytes long. That will blow the range of
double. You have a 1024 range binary exponent = 2^1024 equivaent to
10^308, equivalent to 128 bytes long.

It would be interesting to find out. Put a check in if it is in range,
then convert to double if it is, then do the sqrt, then go back do
bigInteger How does that overhead compare with a some extra rounds of
bigInteger divide?

My intuition is it will pay.

There might even be a way to efficiently scale overweight numbers to
get a double approximation too. You use the 1020 high order bytes.

Keep in mind that even the sqrt might be off the double scale, so you
can't unscale in double format.

Signature

Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Reply to this Message

Andrew Reilly - 02 Aug 2004 00:48 GMT

>>Wouldn't
>>
[quoted text clipped - 11 lines]
> bigInteger How does that overhead compare with a some extra rounds of
> bigInteger divide?

If that's the case, wouldn't 1<<(half number of bits in value), as
a BigInteger be a significantly better guess than value/2?
Value/2 is only near the square root of value when value is near
four...

I don't know the BigInteger class. Does it have a method for
telling you how many bits (or bytes) the number occupies?

Signature

Andrew

Reply to this Message

Roedy Green - 02 Aug 2004 02:22 GMT

>I don't know the BigInteger class. Does it have a method for
>telling you how many bits (or bytes) the number occupies?

There's BigInteger.bitLength();

There are also shiftLeft(n /* bits */) and shiftRight.

Signature

Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.

Reply to this Message

Michael Amling - 02 Aug 2004 02:38 GMT

>>> Wouldn't
>>>
[quoted text clipped - 18 lines]
> I don't know the BigInteger class. Does it have a method for telling
> you how many bits (or bytes) the number occupies?

Yes. A reasonable starting point for sqrt(BigInteger xx) would be
BigInteger guess=BigInteger.valueOf(1).shiftLeft(xx.bitLength()/2).

To incorporate Math.sqrt, you'd have something more like
int blen=xx.bitLength(), rootShift=blen>124?(blen-124)>>1:0;
BigInteger
guess=BigInteger.valueOf(Math.sqrt(xx.shiftRight(rootShift*2).doubleValue()).
longValue()).shiftLeft(rootShift);
and then continue with Newton-Raphson using that initial guess.

--Mike Amling

Reply to this Message

square roots of big integers

Free Magazines