integer square roots

timro21 timro21 at
Thu Jul 23 21:00:20 EDT 2009

On Jul 24, 10:35 am, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> timro21 <timr... at> 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. 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.

More information about the Python-list mailing list