MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Fitting data to line with a specific slope
  • Next by Date: Re: Delete All Output (bug)
  • Previous by thread: Fitting data to line with a specific slope
  • Next by thread: Histogram fitting