integer square roots
timro21 at gmail.com
Thu Jul 23 21:00:20 EDT 2009
On Jul 24, 10:35 am, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> timro21 <timr... at 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
> 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