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.pdf has some advice about how to do that. sci.crypt might be another good place to ask this question. -- http://mail.python.org/mailman/listinfo/python-list
