20070717, 23:49  #1 
Jul 2007
11_{16} 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 nonsquares, then I do a full integer sqrt only if those tests pass. Thanks for any help! 
20070718, 13:29  #2  
Nov 2003
2^{2}·5·373 Posts 
Quote:
I would suggest prebuilding a table of quad. residues mod (say) 3*5*7*11 and checking it first. (or perhaps mod 3465 etc). 

20070718, 18:08  #3  
Jul 2007
17 Posts 
Quote:
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 sweetspots 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:
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! 

20070718, 18:18  #4  
Nov 2003
2^{2}·5·373 Posts 
Quote:


20070718, 19:13  #5 
Cranksta Rap Ayatollah
Jul 2003
641 Posts 

20070718, 20:12  #6 
Tribal Bullet
Oct 2004
DD1_{16} Posts 
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 53bit precision. It's also much better when computing higherorder roots, since using 2^((bits in n)/root) as an initial estimate becomes very inaccurate for root > 5 or so.

20070720, 15:40  #7 
"Michael"
Aug 2006
Usually at home
2·41 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.

20070720, 15:55  #8  
Nov 2003
2^{2}·5·373 Posts 
Quote:
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. 

20070720, 20:45  #9 
Aug 2002
Buenos Aires, Argentina
2^{2}×337 Posts 
You are doing two divisions. If you are using 16 or 32bit 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.

20070720, 20:57  #10  
Aug 2002
Buenos Aires, Argentina
2^{2}×337 Posts 
Quote:
If is an approximation of , the next term in the sequence is: Once you have with the desired approximation, multiply by to get . 

20070721, 16:21  #11 
Bronze Medalist
Jan 2004
Mumbai,India
100000000100_{2} 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 20070721 at 16:25 Reason: Add adjective! 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
determine  hyderman  Homework Help  7  20070617 06:01 
Methods to determine integer multiples  dsouza123  Math  6  20061118 16:10 
Help: trying to determine latency on movaps instructions on AthlonXP  LoKI.GuZ  Hardware  1  20040126 20:05 
Early doublechecking to determine errorprone machines?  GP2  Data  13  20031115 06:59 
How to determine the P1 boundaries?  Boulder  Software  2  20030820 11:55 