mersenneforum.org > Math Determine squares
 Register FAQ Search Today's Posts Mark Forums Read

 2007-07-17, 23:49 #1 fenderbender     Jul 2007 218 Posts 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!
2007-07-18, 13:29   #2
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by fenderbender 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).

2007-07-18, 18:08   #3
fenderbender

Jul 2007

17 Posts

Quote:
 Originally Posted by R.D. Silverman 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 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.

2007-07-18, 18:18   #4
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by fenderbender 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......

2007-07-18, 19:13   #5
Orgasmic Troll
Cranksta Rap Ayatollah

Jul 2003

641 Posts

Quote:
 Originally Posted by R.D. Silverman 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?

2007-07-18, 20:12   #6
jasonp
Tribal Bullet

Oct 2004

5×709 Posts

Quote:
 Originally Posted by fenderbender 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.

 2007-07-20, 15:40 #7 mgb   "Michael" Aug 2006 Usually at home 5216 Posts 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.
2007-07-20, 15:55   #8
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by mgb 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.
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.

2007-07-20, 20:45   #9
alpertron

Aug 2002
Buenos Aires, Argentina

2×3×241 Posts

Quote:
 Originally Posted by fenderbender 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.

2007-07-20, 20:57   #10
alpertron

Aug 2002
Buenos Aires, Argentina

2·3·241 Posts

Quote:
 Originally Posted by fenderbender 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}$.

 2007-07-21, 16:21 #11 mfgoode Bronze Medalist     Jan 2004 Mumbai,India 22×33×19 Posts 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!

 Similar Threads Thread Thread Starter Forum Replies Last Post hyderman Homework Help 7 2007-06-17 06:01 dsouza123 Math 6 2006-11-18 16:10 LoKI.GuZ Hardware 1 2004-01-26 20:05 GP2 Data 13 2003-11-15 06:59 Boulder Software 2 2003-08-20 11:55

All times are UTC. The time now is 17:38.

Fri May 20 17:38:02 UTC 2022 up 36 days, 15:39, 0 users, load averages: 2.16, 1.78, 1.55