On Jul 24, 10:35 am, Paul Rubin <http://phr...@nospam.invalid> wrote: > timro21 <timr...@gmail.com> writes: > > I wish to process billions of 100-digit numbers and test if each has > > an integer square root. What's the most efficient way to do this? > > Is this a homework problem? If not, may I ask what the application is? > > I think the basic answer is 1) use the law of quadratic reciprocity to > eliminate a lot of the inputs quickly (for example, just looking at > the low 8 bits of an input number should eliminate about 5/6th of > them); 2) use GMP and Newton's method to check the > rest.http://cr.yp.to/papers/powers.pdfhas some advice about how to do > that. > > sci.crypt might be another good place to ask this question.
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. -- http://mail.python.org/mailman/listinfo/python-list
