What is the most efficient method for determining whether a given
integer N is a perfect square? One approach would be to check to
see if N is a square modulo several small numbers, which can probably
be done more easily than extracting the full square root. For
example, if we want to find out whether the number
N = 371930958274059827465211239444089
is a square, we can first check the last two decimal digits to see
if they are one of the twenty-two possible squares (mod 100), ten of
which are obvious {00,01,04,09,..,81} and the remaining twelve of
which are {21,24,29,41,44,56,61,69,76,84,89,96}. The chances of a
randomly selected non-square integer passing this test is just 22/100.
Then, taking advantage of the fact that 999999 = 3*3*7*11*13*37, we
can check to see if N is a square modulo each of these primes by
simply forming the sum of the digits of N taken 6 at a time:
444089
211239
827465
274059
930958
371
-------
SUM = 2688181
The squares (mod 9) are {0,1,4,7}, and this SUM is congruent to
7 (mod 9), so we still can't be sure it's non-square. However, it
is congruent to 6 (mod 7), whereas the squares (mod 7) are {0,1,2,4},
so N can't be a square.
In general, I'd expect the probability of a randomly chosen non-square
integer passing the "squareness test" relative to (2^2)(5^2), 3^2, 7,
11, 13, and 37 to be about
22 4 4 6 7 19
P = ---- --- --- ---- ---- ---- = 0.0084
100 9 7 11 13 37
so it will catch over 99% of the non-squares.
Or, we could take advantage of the fact that 1001=7*11*13 and so
1000 = -1 (mod 7*11*13). Thus, if we take the digits of N in groups
of 3, and alternately add and subtract them, we can easily check for
squareness modulo 7, 11, and 13.
So the quickest approach might be to first check the last two decimal
digits for squareness (mod 100), then add up the digits one at a time
and check the sum for squareness (mod 9), and then add up the digits
three at a time (with alternating signs) and check the sum for
squareness modulo 7, 11, and 13. This will catch over 98% of
non-squares.
Return to MathPages Main Menu
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4