Finding perfect squares
- To: mathgroup at smc.vnet.net
- Subject: [mg30605] Finding perfect squares
- From: AGUIRRE ESTIBALEZ Julian <mtpagesj at lg.ehu.es>
- Date: Fri, 31 Aug 2001 04:09:30 -0400 (EDT)
- Organization: Universidad del Pais Vasco/Euskal Herriko Unibertsitatea
- Sender: owner-wri-mathgroup at wolfram.com
I need a function to determine wether a list of integers contains a
square. I am using
Select[mylist, SquareQ, 1] != {}
where SquareQ[n] returns true if n is a perfect square. The naif choice
SquareQ = IntegerQ[Sqrt[#]]&
is very slow for my needs, so I define
SquareQ = JacobiSymbol[#, p1] != -1 && ...&& JacobiSymbol[#, pk] !=-1 &&
Round[Sqrt[N[#, prec]]]^2 == # &
where p1, ..., pk are odd primes. The last test may fail to recognize a
square, but will never return True when applied to a non square.
Increasing prec enlarges the range in which it gives correct results.
Can you suggest a faster way? In my application, my list has
between 10^3 and 10^5 integers with around 40 decimal digits (so that, if
I understand correctly, Complile will not help).
Thanks in advance.
Julian Aguirre | Voice: +34 946012659
Departamento de Matematicas | Fax: +34 944648500
Universidad del Pais Vasco | Postal: Aptdo. 644, 48080 Bilbao, Spain
| email: mtpagesj at lg.ehu.es