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