mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-07-17, 23:49   #1
fenderbender
 
fenderbender's Avatar
 
Jul 2007

17 Posts
Default Determine squares

What is an efficient way to determine if some (large) number is a perfect square?

You can quickly determine if some numbers are NONsquares by looking at remainders modulo different values.. for example, perfect squares all have remainders 0, 1, 4, 9, 16, or 17 mod 32. You can repeat with other bases and keep ruling out cases. Those are not guarantees, though, just ways to rule out numbers efficiently.

But

1) What's the way to prove that you HAVE found a square? I can compute the integer square root, that's certainly sufficient, but seems like overkill and it's not a minor amount of computation for 20 digit numbers, much less 200 digit ones.

2) What's the most EFFICIENT way to combine tests to make the determination fast? Probably using the remainder test with different bases, and only if it passes some number of tests, do the (expensive?) test #1?

Currently in my "good enough" code, I'm checking remainders mod 32 first, then mod 35, then mod 99. Those exclude 90% of non-squares, then I do a full integer sqrt only if those tests pass.

Thanks for any help!
fenderbender is offline   Reply With Quote
Old 2007-07-18, 13:29   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by fenderbender View Post
What is an efficient way to determine if some (large) number is a perfect square?

You can quickly determine if some numbers are NONsquares by looking at remainders modulo different values.. for example, perfect squares all have remainders 0, 1, 4, 9, 16, or 17 mod 32. You can repeat with other bases and keep ruling out cases. Those are not guarantees, though, just ways to rule out numbers efficiently.

But

1) What's the way to prove that you HAVE found a square? I can compute the integer square root, that's certainly sufficient, but seems like overkill and it's not a minor amount of computation for 20 digit numbers, much less 200 digit ones.

2) What's the most EFFICIENT way to combine tests to make the determination fast? Probably using the remainder test with different bases, and only if it passes some number of tests, do the (expensive?) test #1?

Currently in my "good enough" code, I'm checking remainders mod 32 first, then mod 35, then mod 99. Those exclude 90% of non-squares, then I do a full integer sqrt only if those tests pass.

Thanks for any help!
Finding the integer square root IS fast and efficient via Newton-Raphson.

I would suggest pre-building a table of quad. residues mod (say) 3*5*7*11
and checking it first. (or perhaps mod 3465 etc).
R.D. Silverman is offline   Reply With Quote
Old 2007-07-18, 18:08   #3
fenderbender
 
fenderbender's Avatar
 
Jul 2007

17 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I would suggest pre-building a table of quad. residues mod (say) 3*5*7*11
and checking it first. (or perhaps mod 3465 etc).
I start with mod 32 residues since I can read the remainders directly from the stored representation without doing any divisions at all. (So the test speed is dependent just on looking for one of the acceptable 7 remainders.)
There's not much gain going to mod 64 or 128 or higher, though.

Then I use mod 35, which has 12 residues, and next mod 99 which has 24 residues.


Using 3465 (3*3*5*7) is very good indeed, with only 288 residues, so that's 92% rejection right there. WIth so many residues you start needing a lookup table, so it may or may not be better to use multiple smaller tests or not. That becomes very implementation and processor dependent (is computation faster than table lookups?) Other notable sweet-spots for a single test would be 45 (12 residues) 315 (48 residues), and 17325 (1056 residues). The best set of multiple sequential tests is going to be even more implementation dependent.. testing mod 32 followed by 35 followed by 99 gives 98.2% rejection with only small tables.


Quote:
Originally Posted by R.D. Silverman View Post
Finding the integer square root IS fast and efficient via Newton-Raphson.
My number theory knowlege is so weak, I had no idea if there was a better way to prove squaritude.

Yes, integer square roots are very efficient, only about log2 divides are necessary, and you can even speed those divides up enormously by using only partial words for each iteration, so you only need a full division for the last two steps or so.
Also, using a smart starting guess can start convergence much faster.. you can probably read the number of words in the value to roughly estimate the magnitude of n as 2^b, and make a starting guess of 2^(b/2) based on that.


I know that I"m not doing anything new, surely hundreds of recreational coders have gone through this, but it's still fun to just play with the math and the code.

Thanks for the reply!
fenderbender is offline   Reply With Quote
Old 2007-07-18, 18:18   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by fenderbender View Post
I start with mod 32 residues since I can read the remainders directly from the stored representation without doing any divisions at all. (So the test speed is dependent just on looking for one of the acceptable 7 remainders.)
There's not much gain going to mod 64 or 128 or higher, though.

Then I use mod 35, which has 12 residues, and next mod 99 which has 24 residues.


Using 3465 (3*3*5*7) is very good indeed, with only 288 residues, so that's 92% rejection right there. WIth so many residues you start needing a lookup table, so it may or may not be better to use multiple smaller tests or not. That becomes very implementation and processor dependent (is computation faster than table lookups?) Other notable sweet-spots for a single test would be 45 (12 residues) 315 (48 residues), and 17325 (1056 residues). The best set of multiple sequential tests is going to be even more implementation dependent.. testing mod 32 followed by 35 followed by 99 gives 98.2% rejection with only small tables.



My number theory knowlege is so weak, I had no idea if there was a better way to prove squaritude.

Yes, integer square roots are very efficient, only about log2 divides are necessary, and you can even speed those divides up enormously by using only partial words for each iteration, so you only need a full division for the last two steps or so.
Also, using a smart starting guess can start convergence much faster.. you can probably read the number of words in the value to roughly estimate the magnitude of n as 2^b, and make a starting guess of 2^(b/2) based on that.


I know that I"m not doing anything new, surely hundreds of recreational coders have gone through this, but it's still fun to just play with the math and the code.

Thanks for the reply!
It appears that you are doing everything just right......
R.D. Silverman is offline   Reply With Quote
Old 2007-07-18, 19:13   #5
Orgasmic Troll
Cranksta Rap Ayatollah
 
Orgasmic Troll's Avatar
 
Jul 2003

10100000012 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
It appears that you are doing everything just right......
Mods, is there a way we can give fenderbender some sort of forum medal for this?
Orgasmic Troll is offline   Reply With Quote
Old 2007-07-18, 20:12   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22·883 Posts
Default

Quote:
Originally Posted by fenderbender View Post
Also, using a smart starting guess can start convergence much faster.. you can probably read the number of words in the value to roughly estimate the magnitude of n as 2^b, and make a starting guess of 2^(b/2) based on that.
An even better method is to use the top few words of n to compute log(n), divide that by 2, then convert back to multiple precision by computing 2.0^(mantissa of result), converting to arbitrary precision, and shifting up the required number of places. This would save you having to do the first ~5 Newton iterations, since you start with the square root to 53-bit precision. It's also much better when computing higher-order roots, since using 2^((bits in n)/root) as an initial estimate becomes very inaccurate for root > 5 or so.
jasonp is offline   Reply With Quote
Old 2007-07-20, 15:40   #7
mgb
 
"Michael"
Aug 2006
Usually at home

24·5 Posts
Default

A perfect square must produce a quadratic residue for every prime. If it fails (use Euler's Criterion) for only one prime it is not square. If it produces a qr. for n primes the chances that it is not square is only 1/2^n so if you test, say, 100 primes and it produces a qr. for each of them, then the chances it is not square is only 1 in 2^100.
mgb is offline   Reply With Quote
Old 2007-07-20, 15:55   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by mgb View Post
A perfect square must produce a quadratic residue for every prime. If it fails (use Euler's Criterion) for only one prime it is not square. If it produces a qr. for n primes the chances that it is not square is only 1/2^n so if you test, say, 100 primes and it produces a qr. for each of them, then the chances it is not square is only 1 in 2^100.
Thanks for telling us what everyone already knew. Almost. Your statement
is not 100% correct. See, for example: Shanks "Solved and Unsolved
Problems in Number Theory" , section 67. The probabilities are not quite
independent. The probability is NOT 1/2^100.

And you miss the main point of the discussion. The issue is how to do it
QUICKLY. Doing 100 q.r. tests will be EXPENSIVE; more expensive than
computing the actual square root.
R.D. Silverman is offline   Reply With Quote
Old 2007-07-20, 20:45   #9
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

2×3×223 Posts
Default

Quote:
Originally Posted by fenderbender View Post
Currently in my "good enough" code, I'm checking remainders mod 32 first, then mod 35, then mod 99. Those exclude 90% of non-squares, then I do a full integer sqrt only if those tests pass.
You are doing two divisions. If you are using 16- or 32-bit arithmetic it is better to divide the original number first by 35*99 and then subject the result to the mod 35 and mod 99 tests.
alpertron is offline   Reply With Quote
Old 2007-07-20, 20:57   #10
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

101001110102 Posts
Default

Quote:
Originally Posted by fenderbender View Post
Yes, integer square roots are very efficient, only about log2 divides are necessary, and you can even speed those divides up enormously by using only partial words for each iteration, so you only need a full division for the last two steps or so.
There is no need for division when computing square roots, they can be computed using multiplications only, so you can use Karatsuba or faster approaches.

If x_n is an approximation of 1/\sqrt{N}, the next term in the sequence is:

\large x_{n+1} = \frac{x_n}{2}(3 - N*x_n^2)

Once you have 1/\sqrt{N} with the desired approximation, multiply by N to get \sqrt{N}.
alpertron is offline   Reply With Quote
Old 2007-07-21, 16:21   #11
mfgoode
Bronze Medalist
 
mfgoode's Avatar
 
Jan 2004
Mumbai,India

22×33×19 Posts
Lightbulb Starting guess!

[QUOTE=fenderbender;110645]I start with mod 32 residues since I can read .
~ ~
My number theory knowlege is so weak, I had no idea if there was a better way to prove squaritude.

~ ~
Also, using a smart starting guess can start convergence much faster.. you QUOTE]



First of all you can start by inspection of the huge number.

If the last two digits of the number are any one of these, 22 in all possibilities, the chances are it could be a square

viz: 00 , 01 , 04 , 09 , 16 , 21 , 24 , 25 , 29 , 36 , 41 , 44 , 49 , 56 , 61 , 64 , 69 , 76 , 81 , 84 , 89 , and last 96.

These numbers above are the last two digits got by squaring numbers from 0 to 99 and can be easily remembered !

Also if you prefer division, The square of any number is either divisible by 4 for an even number or leaves a remainder 1 for odd numbers.

Of course there are many more exceptions e.g. 123456 which satisfies both conditions but is not a square number.

Mally

Last fiddled with by mfgoode on 2007-07-21 at 16:25 Reason: Add adjective!
mfgoode is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
determine hyderman Homework Help 7 2007-06-17 06:01
Methods to determine integer multiples dsouza123 Math 6 2006-11-18 16:10
Help: trying to determine latency on movaps instructions on AthlonXP LoKI.GuZ Hardware 1 2004-01-26 20:05
Early double-checking to determine error-prone machines? GP2 Data 13 2003-11-15 06:59
How to determine the P-1 boundaries? Boulder Software 2 2003-08-20 11:55

All times are UTC. The time now is 18:19.

Fri Dec 4 18:19:39 UTC 2020 up 1 day, 14:30, 0 users, load averages: 1.29, 1.36, 1.46

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.