integer square roots

[casevh]

> 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.
>
gmpy.is_square() is quite fast. On a older 32-bit Linux box, it can
test approximately 400,000 100-digits numbers per second. The time
includes conversion from a string. If the numbers are already Python
longs, it can check 800,000 per second. Checking a billion is not
unreasonable.

casevh