timro21 <timr...@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. -- http://mail.python.org/mailman/listinfo/python-list
