 |
AppletTalk.com
Java discussions newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Andrew Thompson
Guest
|
 Posted: Tue Jul 20, 2004 4:41 pm Post subject: Re: square roots of big integers |
 |
|
On Tue, 20 Jul 2004 17:26:55 GMT, Jeremy Watts wrote:
| Quote: | 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. ;-)
--
Andrew Thompson
http://www.PhySci.org/ Open-source software suite
http://www.PhySci.org/codes/ Web & IT Help
http://www.1point1C.org/ Science & Technology
|
|
| Back to top |
|
 |
Jeremy Watts
Guest
|
| Posted: Tue Jul 20, 2004 5:26 pm Post subject: square roots of big integers |
|
|
hi,
i know about javas 'big integer' for handling of large integers, but
wondered whether it can find square roots of large numbers also?
|
|
| Back to top |
|
|
Ian Shef
Guest
|
| Posted: Tue Jul 20, 2004 7:21 pm Post subject: Re: square roots of big integers |
|
|
Andrew Thompson <SeeMySites (AT) www (DOT) invalid> wrote in
news:1scydzro573yt.xua9emwcapho.dlg (AT) 40tude (DOT) net:
but BigInteger does support add, subtract, multiply, and divide, so I suppose
that a Newton-Raphson iteration or other method could be implemented.
--
Ian Shef
These are my personal opinions and not those of my employer.
|
|
| Back to top |
|
|
Roedy Green
Guest
|
| Posted: Tue Jul 20, 2004 8:26 pm Post subject: Re: square roots of big integers |
|
|
On Tue, 20 Jul 2004 17:26:55 GMT, "Jeremy Watts"
<jwatts1970 (AT) hotmail (DOT) com> wrote or quoted :
| Quote: | 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.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
|
|
| Back to top |
|
|
Ian Shef
Guest
|
| Posted: Wed Jul 21, 2004 6:43 pm Post subject: Re: square roots of big integers |
|
|
Roedy Green <look-on (AT) mindprod (DOT) com.invalid> wrote in
news:sovqf09nkecht494spd83dl6e0h7jafmh3 (AT) 4ax (DOT) com:
| Quote: | On Tue, 20 Jul 2004 17:26:55 GMT, "Jeremy Watts"
[email]jwatts1970 (AT) hotmail (DOT) com[/email]> wrote or quoted :
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.
|
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.
--
Ian Shef
These are my personal opinions and not those of my employer.
|
|
| Back to top |
|
|
Ian Shef
Guest
|
| Posted: Wed Jul 21, 2004 6:47 pm Post subject: Re: square roots of big integers |
|
|
Ian Shef <invalid (AT) avoiding (DOT) spam> wrote in
news:Xns952D774243D77vaj4088ianshef (AT) 138 (DOT) 126.254.210:
| Quote: | Roedy Green <look-on (AT) mindprod (DOT) com.invalid> wrote in
news:sovqf09nkecht494spd83dl6e0h7jafmh3 (AT) 4ax (DOT) com:
On Tue, 20 Jul 2004 17:26:55 GMT, "Jeremy Watts"
[email]jwatts1970 (AT) hotmail (DOT) com[/email]> wrote or quoted :
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.
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.
.... 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.
--
Ian Shef
These are my personal opinions and not those of my employer.
|
|
| Back to top |
|
|
Roedy Green
Guest
|
| Posted: Wed Jul 21, 2004 7:23 pm Post subject: Re: square roots of big integers |
|
|
On Wed, 21 Jul 2004 18:43:25 GMT, Ian Shef <invalid (AT) avoiding (DOT) spam>
wrote or quoted :
| Quote: |
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.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
|
|
| Back to top |
|
|
Ian Shef
Guest
|
| Posted: Wed Jul 28, 2004 7:11 pm Post subject: Re: square roots of big integers |
|
|
=?UTF-8?b?TMSByrtpZSBUZWNoaWU=?= <laie (AT) win_remove_get_nospam_solutions (DOT) com>
wrote in news:pan.2004.07.28.06.28.33.460506
@win_remove_get_nospam_solutions.com:
| Quote: | On Tue, 20 Jul 2004 19:21:58 +0000, Ian Shef wrote:
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 ?
--
Ian Shef
These are my personal opinions and not those of my employer.
|
|
| Back to top |
|
|
Michael Amling
Guest
|
| Posted: Wed Jul 28, 2004 11:46 pm Post subject: Re: square roots of big integers |
|
|
Ian Shef wrote:
| Quote: | =?UTF-8?b?TMSByrtpZSBUZWNoaWU=?=
wrote in news:pan.2004.07.28.06.28.33.460506
@win_remove_get_nospam_solutions.com:
On Tue, 20 Jul 2004 19:21:58 +0000, Ian Shef wrote:
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.
|
If the square root of an integer is not itself an integer then the
exact answer can't be represented by BigDecimal.
| Quote: | 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
|
|
| Back to top |
|
|
Roedy Green
Guest
|
| Posted: Sun Aug 01, 2004 10:26 pm Post subject: Re: square roots of big integers |
|
|
On Sun, 1 Aug 2004 23:25:11 +0200, "Boudewijn Dijkstra"
<usenet (AT) bdijkstra (DOT) tmfweb.nl> wrote or quoted :
| Quote: |
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.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
|
|
| Back to top |
|
|
Andrew Reilly
Guest
|
| Posted: Sun Aug 01, 2004 11:48 pm Post subject: Re: square roots of big integers |
|
|
Roedy Green wrote:
| Quote: | On Sun, 1 Aug 2004 23:25:11 +0200, "Boudewijn Dijkstra"
[email]usenet (AT) bdijkstra (DOT) tmfweb.nl[/email]> wrote or quoted :
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?
|
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?
--
Andrew
|
|
| Back to top |
|
|
Roedy Green
Guest
|
| Posted: Mon Aug 02, 2004 1:22 am Post subject: Re: square roots of big integers |
|
|
On Mon, 02 Aug 2004 09:48:07 +1000, Andrew Reilly
<areilly-newspost (AT) areilly (DOT) bpc-users.org> wrote or quoted :
| Quote: | 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.
--
Canadian Mind Products, Roedy Green.
Coaching, problem solving, economical contract programming.
See http://mindprod.com/jgloss/jgloss.html for The Java Glossary.
|
|
| Back to top |
|
|
Michael Amling
Guest
|
| Posted: Mon Aug 02, 2004 1:38 am Post subject: Re: square roots of big integers |
|
|
Andrew Reilly wrote:
| Quote: | Roedy Green wrote:
On Sun, 1 Aug 2004 23:25:11 +0200, "Boudewijn Dijkstra"
[email]usenet (AT) bdijkstra (DOT) tmfweb.nl[/email]> wrote or quoted :
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?
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?
|
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
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
