Re: Integer test for perfect square
- From: Tim Smith <reply_in_group@xxxxxxxxxxxxxxxx>
- Date: Thu, 12 Mar 2009 18:15:02 -0700
In article
<13957920.1236879700767.JavaMail.jakarta@xxxxxxxxxxxxxxxxxxxxxx>,
riderofgiraffes <mathforum.org_am@xxxxxxxxxxxxxx> wrote:
Are you sure? Have you tested that? Newton's method
doubles the nubmer of digits on each iteration, but
the "long-division" method that I know so well only
gives one extra digit per phase. My speed tests show
integer variants of Newton's Method to be far faster
for large numbers.
In short, my results disagree with your assertion, and
I would be interested to see how your evidence comapares
with my tests.
Note that Newton's speed depends a lot on the initial approximation.
Consider this straightforward, if a bit ugly, implementation in
Mathematica finds Floor[Sqrt[n]]:
r = 1
For[i = 1, i < 10000, ++i,
sr = r;
r = Floor[(r + Floor[n/r])/2];
If[sr <= r && i > 1, Print[{i, sr}]; Break[]];
]
For 1000 digit numbers, this takes around 1600 iterations. Similar if
you start with r = n or r = n/2.
(I'm talking about decimal digits here, not binary digits).
Change the initialization to
r = 10^(Floor[(Length[IntegerDigits[n]] - 1)/2])
and then it only take around 12 iterations.
The IntegerDigits function return a list of the digits of the argument,
and Length returns the number of elements in the list, so
Length[IntegerDigits[n]] is simply the number of digits in n.
For numbers in the range [2^31, 2^32], it is about 20 iterations
starting with r = 1, and 7 starting with the better approximation.
If working in a language where it is easy to get the number of binary
digits in a number, then
r = 2^(Floor[(Length[IntegerDigits[n,2]] - 1)/2])
cuts off a couple more iterations.
--
--Tim Smith
.
- References:
- Re: Integer test for perfect square
- From: bert
- Re: Integer test for perfect square
- From: riderofgiraffes
- Re: Integer test for perfect square
- Prev by Date: Re: Hyperbolic Only for (x^3 + Px + Q = 0)
- Next by Date: Re: Hyperbolic Only for (x^3 + Px + Q = 0)
- Previous by thread: Re: Integer test for perfect square
- Next by thread: Re: Integer test for perfect square
- Index(es):
Relevant Pages
|
