integer square roots

[timro21]

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?

 

[Mensanator]

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?

Use gmpy.

Help on built-in function sqrt in module gmpy:

sqrt(...)
sqrt(x): returns the integer, truncated square root of x, i.e. the
largest y such that x>=y*y. x must be an mpz, or else gets coerced
to one; further, x must be >= 0.

mpz
(10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000267)

mpz(100000000000000000000000000000000000000000000000000)

 

[Mensanator]

Use gmpy.


Help on built-in function sqrt in module gmpy:

sqrt(...)
    sqrt(x): returns the integer, truncated square root of x, i.e. the
    largest y such that x>=y*y. x must be an mpz, or else gets coerced
    to one; further, x must be >= 0.


mpz(100000000000000000000000000000000000000000000000000)

Duh. I completely misread this. I thought you wanted the square root,
not IF it had a square root that's an integer.

Sorry about that.

Try this, instead:
(mpz(100000000000000000000000000000000000000000000000000), mpz(267))

It has a non-zero remainder, so it's not an integer square root.

 

[Mensanator]

Duh. I completely misread this. I thought you wanted the square root,
not IF it had a square root that's an integer.

Sorry about that.

Try this, instead:


(mpz(100000000000000000000000000000000000000000000000000), mpz(267))

It has a non-zero remainder, so it's not an integer square root.

There's also

is_square(...)
is_square(x): returns 1 if x is a perfect square, else 0.
x must be an mpz, or else gets coerced to one.

 

[Paul Rubin]

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.

 

[timro21]

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.

 

[Paul Rubin]

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.

 

[casevh]

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.

gmpy.is_square() is quite fast. On a older 32-bit Linux box, it can
test approximately 400,000 100-digits numbers per second. The time
includes conversion from a string. If the numbers are already Python
longs, it can check 800,000 per second. Checking a billion is not
unreasonable.

casevh

 

[Paul Rubin]

gmpy.is_square() is quite fast. On a older 32-bit Linux box, it can
test approximately 400,000 100-digits numbers per second. The time
includes conversion from a string. If the numbers are already Python
longs, it can check 800,000 per second. Checking a billion is not
unreasonable.

Wow, that is pretty impressive. A look at the code shows it uses
quite a few optimizations:

http://sage.math.washington.edu/home/novoselt/gmp-4.2.4/mpn/perfsqr.c

 

[timro21]

Thanks to all!

Tim

 

[Tim Daneliuk]

Thanks to all!

Tim

While we're at it, would you mind saying more about what exactly you're
doing - Inquiring Math Dorks (tm) want to know ...

 

[timro21]

Hi Tim, sure, I'm looking at the perfect cuboid problem.

I've just spent a couple of very frustrating hours. Given that I'm in
my 50's but have the brain of a retarded 3-year-old, can someone
please explain what I have to do to download gmpy to use with
ActivePython 2.6 on a Windows system? I downloaded (or so I thought)
GMPY 1.04 from http://code.google.com/p/gmpy/ but all the files look
way too small...and then how do I import it into a Python
program...I'm sure I could do this if it wasn't for my extreme
stupidity...

 

[casevh]

Hi Tim, sure, I'm looking at the perfect cuboid problem.

I've just spent a couple of very frustrating hours.  Given that I'm in
my 50's but have the brain of a retarded 3-year-old, can someone
please explain what I have to do to download gmpy to use with
ActivePython 2.6 on a Windows system?  I downloaded (or so I thought)
GMPY 1.04 fromhttp://code.google.com/p/gmpy/but all the files look
way too small...and then how do I import it into a Python
program...I'm sure I could do this if it wasn't for my extreme
stupidity...

You should just download the Windows installer from the Downloads tab.
I would recommend version 1.10 since it should be faster and fixes
some bugs in 1.04. The direct link is

http://gmpy.googlecode.com/files/gmpy-1.10-beta.win32-py2.6.exe

Just run the installer and it should automatically detect your
existing Python installation. The executable is small. ;-)

casevh

p.s. If you're using a 64-bit Windows system, let me know and I'll
step you through the manual process.

 

[timro21]

Bloody 'ell - thanks.