integer square roots

[Paul Rubin]

timro21 <timro21 at gmail.com> writes:
> Homework?  Gosh no.  I have several number theory applications which
> need to know (quickly) whether particular very large numbers are
> perfect squares.  Since I asked this in this newsgroup I guess I
> assumed that responses wuld relate specifically to how to do this
> efficiently *and accurately* in Python.  Sorry if I wasn't clear.

comp.lang.python is a good place to get answers about Python.  It's
probably not such a good source of answers about computational number
theory.  Also, Python is more about productivity than speed, so
answers involving Python may not be the most efficient possible
answers.  One obvious point though is that GMP/gmpy is pretty simple
to use from Python and will be several times faster than Python's
built in longs.  Also, as Mensanator pointed out, GMP has built-in
functions that will help you with precise checks (I'd forgotten or not
known about them).  I still think you'd get a speedup from first
filtering out obviously non-square candidates before resorting to
multi-precision arithmetic.  Some other fairly simple optimization may
be possible too.

I asked about the application mainly because I wondered if you had
realtime requirements, whether you were going to have to keep doing
this problem with new numbers, etc.  If you just have a 1-off task of
checking a few billion numbers, you could probably do it in a few days
with Python on a workstation using some fairly simple code.  If you
want to check billions of numbers per minute, or if what you really
want is to check trillions of numbers rather than billions, then it's
worth pursuing fancier methods.  Another issue is the source of the
numbers.  E.g. maybe there is a way to program a graphics accelerator
to turn a number into a list of residues mod a bunch of small primes
in parallel and get a fast, near-certain test if the inputs are
random, but that approach could be fooled if the numbers were
concocted by a possible adversary.