Re: Testing for squares
- To: mathgroup at smc.vnet.net
- Subject: [mg66244] Re: Testing for squares
- From: "Ray Koopman" <koopman at sfu.ca>
- Date: Fri, 5 May 2006 05:02:44 -0400 (EDT)
- References: <e3cimv$a3k$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
In[1]:= test1 = IntegerQ[Sqrt[#]]&;
test2 = Compile[{{n,_Integer}},Round[Sqrt[N[n]]]^2 === n];
v = Range[123456];
Timing[a = test1/@v;]
Timing[b = test2/@v;]
a === b
Out[4]= {3.49 Second,Null}
Out[5]= {0.34 Second,Null}
Out[6]= True
Julian Aguirre wrote:
> Hi all,
>
> 1) I would like to have an efficient test to decide if an integer is a
> square.
>
> test1 = IntegerQ[Sqrt[#]]&
>
> is too slow for my needs. I am using something like
>
> test2 = Positive[#] && JacobiSymbol[#, p] && Sqrt[Round[N[#,
> precission]]]^2==# &
>
> where p is a prime (or I may use several primes). However test2 may
> return False for very large integers. How large depends on the value of
> precission. Do you know of a faster test?
>
> 2) Let MyList be a large list of integers (somewhere between 20.000 and
> 50.000 elements) and MyTest a function on the integers returning True
> or False (for instance, test2 above). What is an efficient way of
> deciding if there is an element in MyList for which MyTest is True?
> Right now I use
>
> Select[MyList, MyTest, 1] != {}
>
> but may be some of you can provide a better way.
>
> Thanks for any help,
>
> Julián Aguirre