Determine squares

fenderbender · 2007-07-17, 23:49

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!

R.D. Silverman · 2007-07-18, 13:29

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).

fenderbender · 2007-07-18, 18:08

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.

Thanks for the reply!

R.D. Silverman · 2007-07-18, 18:18

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......

Orgasmic Troll · 2007-07-18, 19:13

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?

jasonp · 2007-07-18, 20:12

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.

mgb · 2007-07-20, 15:40

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.

R.D. Silverman · 2007-07-20, 15:55

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.

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.

alpertron · 2007-07-20, 20:45

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.

alpertron · 2007-07-20, 20:57

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}$ .

mfgoode · 2007-07-21, 16:21

[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

2007-07-21, 16:21	#11
mfgoode Bronze Medalist Jan 2004 Mumbai,India 2²×3³×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
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

2007-07-17, 23:49	#1
fenderbender Jul 2007 17 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-20, 15:40	#7
mgb "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.