Detecting perfect squares faster than by extracting square root

Question

Given the radix-$r$ representation of a integer $n$, and a small integer constant $k$, there is an $O(\log n)$ algorithm for detecting whether $n$ is a multiple of $k$, namely, division, which produces as a byproduct the quotient $\lfloor n/k\rfloor$. In general this is the best one can do. But for certain choices of $r$ and $k$, for example $r=10$ and $k=2$, there is an algorithm which answers the question much faster (constant time) without producing the quotient.

Given the radix-$r$ representation of a integer $n$, we can extract the integer square root $\lfloor\sqrt n\rfloor$ in something like $O(\log^3 n)$ time by doing binary search, which Joriki notes below can be improved to $O(\log^2 n)$ with a sufficiently clever implementation. This gives an $O(\log^2 n)$ algorithm for determining whether $n$ is a perfect square.

Is there a significantly faster algorithm which correctly decides whether $n$ is perfect square, without also producing the square root? I suspect not, but I would be interested to see a proof.

Answer 1

See the paper by Bernstein, Lenstra, and Pila: Detecting Perfect Powers by Factoring into Coprimes, Mathematics of Computation, Volume 76, #257, January 2007, pp. 385-388. Or here.

From the abstract: This paper presents an algorithm that, given an integer n>1, finds the largest k such that n is a kth power.

The algorithm runs in time $\log(n)(\log\log(n))^{O(1)}$.

Answer 2

Here is a probabilistic test for squaredness that can achieve an arbitrarily small error with time complexity very close to $\mathcal{O}$(log $n$) base $r$. It's sort of a generalization of the approach used in the GMP library.

Premise 1: If an integer $n$ is a perfect square and $P$ is an odd prime < N, then $n$ (mod $P$) is a quadratic residue modulo $P$.

Contrapositive: If $n$ (mod $P$) is a quadratic non-residue modulo $P$, then $n$ is not a perfect square.

Premise 2: Given an odd prime modulus $P$, there are $\frac{(P+1)}{2}$ quadratic residues (including 0) and $\frac{(P-1)}{2}$ quadratic non-residues. So there's about a 50% probability that a random integer $n$ is a quadratic residue (mod $P$).

We can infer the following. Given an integer $n$:

• If $n$ is a perfect square, then it will pass Euler's criterion for 100% of odd primes coprime to $n$ (see footnote [1]).
• If $n$ is not a perfect square, then it will fail Euler's criterion for roughly 50% of odd primes.

So we can construct a robust probabilistic test in the same style as the Fermat primality test. We pick a prime $P_{0}$ and check Euler's criterion for $n$ (mod $P_{0}$).

• If $n$ is a quadratic non-residue (mod $P_{0}$), then we have our answer definitively, i.e. $n$ is not a perfect square.
• On the other hand, if $n$ is a quadratic residue (mod $P_{0}$), then $n$ may or may not be a perfect square. But we pick more primes $P_{i}$ and perform the test repeatedly.

Each time $n$ passes as a quadratic residue, the intersected probability of $n$ being non-square decreases by 50%, so that it takes only 10 tests to determine that $n$ is a perfect square with >99.9% probability[2], regardless of its size. In other words, if $n$ is not a perfect square, then at least one of the tests will have failed before that point (with >99.9% probability).

The key here is that non-squares always fail the criterion at a ~50% rate (tested against various primes). So if after a dozen-or-so such tests $n$ hasn't failed the criterion even once, there is a very high probability that it is a perfect square. I realize I'm seriously lacking the proper Bayesian terminology here, but this works and you can try it. The error probability can be made arbitrarily small by testing against more primes.

Time complexity: Since the choice of primes $P_{i}$ need not depend on $n$, determining the exponents for the tests takes $\mathcal{O}(1)$ I think. And since the desired confidence level is also independent of $n$, the overall time complexity seems equivalent to that of modular exponentiation. Using the method of exponentiation by squaring with an efficient multiplication algorithm such as k-way Toom-Cook or Schonhage-Strassen gives an overall time complexity very close to $\mathcal{O}$(log $n$) base $r$, depending on parameters chosen. See the linked Wikipedia articles for details.

[1]: Euler's criterion requires that $n$ and $P$ are coprime; if they are not, then $n^{\frac{P-1}{2}}\equiv 0$ (mod $P$), and the test result is discarded.

[2]: A 0.1% error rate on 1 billion integers (of any magnitude) represents around 1 million false positives, which is really bad. Theoretically, 30 primes should be used in order to yield fewer than 1 false positive for every billion integers tested, but in practice I've found that just the first 18-20 primes is sufficient to yield none.

---

Update: Here's a working implementation in C with libgmp:

https://web.archive.org/web/20201030060901/https://gist.github.com/jrodatus/e66d6f6b2f014f6b69543019edd23982

Example Run 1 - Residue statistics:

Test Mode

  0. Statistics for N > P being a quadratic residue mod P
  1. Probable perfect square algorithm

Enter test [0|1] 0
Number of primes: 30  
Number of tests (T): 1000000
Upper bound for N: 100000000000000000

Generating 30 primes...
Done: P_max=127

================================================================================
We will test T=1000000 random integers N, where:

    P_max = 127 < N <= 100000000000000000

Each row P shows the number of these N's that were quadratic residues (mod P),
written as a fraction of T.

If ~50% of randomly-chosen N's were residues (mod P),
that suggests a probability of 50% that a given N > P will be a residue.

Consistent with the Law of Large Numbers,
a large T (e.g. >1000) is needed to converge to this result.
================================================================================
  P   fraction of N's that were residues
----------------------------------------
  3   0.332975000 (332975/1000000)
  5   0.400004000 (400004/1000000)
  7   0.429508000 (429508/1000000)
 11   0.455161000 (455161/1000000)
 13   0.461268000 (461268/1000000)
 17   0.469941000 (469941/1000000)
 19   0.473873000 (473873/1000000)
 23   0.478612000 (478612/1000000)
 29   0.482535000 (482535/1000000)
 31   0.483060000 (483060/1000000)
 37   0.487377000 (487377/1000000)
 41   0.487871000 (487871/1000000)
 43   0.489587000 (489587/1000000)
 47   0.489378000 (489378/1000000)
 53   0.490486000 (490486/1000000)
 59   0.491197000 (491197/1000000)
 61   0.491372000 (491372/1000000)
 67   0.492079000 (492079/1000000)
 71   0.493632000 (493632/1000000)
 73   0.494255000 (494255/1000000)
 79   0.493439000 (493439/1000000)
 83   0.494264000 (494264/1000000)
 89   0.495205000 (495205/1000000)
 97   0.494529000 (494529/1000000)
101   0.494480000 (494480/1000000)
103   0.494896000 (494896/1000000)
107   0.494841000 (494841/1000000)
109   0.496449000 (496449/1000000)
113   0.494854000 (494854/1000000)
127   0.495656000 (495656/1000000)

(Scroll the code box to see all the prime rows, up to P=127.)

The ~30% statistic for P=3, is simply because 3 has only 1 quadratic residue (namely, 1).

---

Example Run 2 - Determining perfect squares:

Test Mode

  0. Statistics for N > P being a quadratic residue mod P
  1. Probable perfect square algorithm

Enter test [0|1] 1
Number of primes: 20
Number of tests (T): 10000000
Upper bound for N: 10000000000000000

Generating 20 primes...
Done: P_max=73

Testing 10000000 random values of N, 73 < N <= 10000000000000000...
# primes          : 20
# N's tested      : 10000000
# false positives : 23
success rate      : 0.999997700

Answer 3

Since this is on the math forum and not one of the many programming forums, I am going to give a pure mathematical answer. If you want my answer to a programming version of this question, in Python, see the stackoverflow site and/or visit the comments below.

One thing you could do to save time and effort is to eliminate the number from consideration as a perfect square by verifying quickly that it isnt one. What I mean is, Im not going to extract the root, nor am I going to verify if a number is a perfect square, but I am going to verify that a number is NOT a perfect square. Some of these hints are almost effortless, you can run these as a precursor to any more complicated algorithm. After all, it makes no sense wasting time and effort on a complicated algorithm when you can prove a number is not a perfect square with a simpler one.

So, you need to know some of the cool and interesting properties of perfect squares, if you dont already.

Firstly, any perfect square ending in 0, or a set of zeros, must contain an even number of terminating zeros. So if the number of zeros trailing the least significant digits of an integer are in odd quantity, it is not a perfect square. 57,000 is not a perfect square. If there is an even number of zeros, you can ignore them entirely and reduce your test number to the digits that precede the string of zeros - we can test 640,000 and 820,000 for perfect squareness by testing just the 64 and 82.

A similar thing can be done in binary. If dealing in programming, you can easily test for factors of $4=2^2$ and scale down using bit-wise operations. In Python I prefer the n&3 == 0 conditional test, and the n >> 2 operation. This is effectively the same thing as the previous test, except in digital/binary logic where the base is 2 instead of 10.

Secondly, all perfect squares end in the numbers 0, 1, 4, 5, 6, or 9. You can ignore the 0 if you observe rule number 1 first. This is a necessary condition. Recognize this is a mod 10 operation. So, if your test number ends (units digit) in a 2, 3, 7, or 8, this is sufficient to say that the number is not a perfect square. For example, the number 934,523 is obviously not a perfect square. See that? With this rule we've already eliminated two-fifth of all possible numbers.

The last two digits of a test number cannot both be odd. 34,833,879 is not a perfect square because both 7 and 9 are odd.

If the test number ends in a 1 or a 9, the two-digit number preceding it HAS to be a multiple of 4. Examples include 81, and the number 57,121 (because 5,712 is a multiple of 4). Numbers like 24621 are not perfect squares because 62 is not a multiple of 4.

If the test number ends in a 4, the digit preceding it has to be even. If not even then not a perfect square. 23,074 is not a perfect square.

If the test number ends in a 6, the digit preceding it has to be odd. If not odd then not a perfect square. 56,846 is not a perfect square.

If the test number ends in a 5, the digit preceding it has to a 2. Furthermore, the digit(s) preceding that 2 has to be either a 0, another 2, or the digits 06 or 56. The number 331,625 is not a perfect square.

Now for some modulo arithmetic. These can be done on paper or in your head and so dont require computers.

A perfect square must be equivalent to 0, 1, or 4 in mod 8. If not, you know you dont have a perfect square. But if you do have a perfect square, the 0,1,or 4 provides you with useful information about the square root. If you get a 1 in mod 8 then your root is odd, if 0 in mod 8 the root is a multiple of 4, if 4 in mod 8 then the root is just even but not a multiple of 4.

Speaking of mod 8 tests, in binary logic we can employ bit-wise operations. If expressed in binary, the smallest three digits of a perfect square always ends in 001, i.e. n&7 == 1. This is true after having factored out all powers of 4 (test 1 binary variation), otherwise n&3 == 0 could be true too.

There is the mod 9 test. Results have to be 0, 1, 4, or 7 in mod 9. If not (2,3,5,6,8) then you dont have a perfect square. The number 56,430,143 is not a perfect square; I know because the 56,430,143 % 9 = 8. Alternatively, look up "digital root" (sum of the digits, repeated, to a singular value), essentially the same as the mod 9 test. If your value is 2, 3, 5, 6 or 8 then it is not a perfect square, but it could be if you have 1,4,7,9.

In mod 13, all perfect squares are equivalent to 0,1,3,4,9,10,12; and in mod 7 they must be equivalent to 1,2,4. FYI.

Also, observe that $(n+1)^2 = n^2 + 2n + 1$. Clearly if your test number $N\in (n^2,n^2+2n+1)$ then it lies between two consecutive perfect squares. If $n,n^2$ are known, for some largest $n^2<N$, it would be pretty easy to reject any value in this interval.

At this point, if your test number has not failed any of the tests, then and only then would I put the resources into root extraction or other complicated algorithms. These tests above use little more than comparison, conditionals, counting, and single-digit additions, some can even be done with bit-logic.

I hope this information helps you and others wanting guidance on this.

Id also like to point out that any prime factor of your test number that comes in an odd multiplicity is also not a perfect square. This is a more time consuming approach though. You need only check primes between 2 and sqrt(n). If you find a prime that divides into n, but does so only an odd number of times, you do not have a square number. Take the perfect square 99,225. Its prime factored into [3,3,3,3,5,5,7,7], with an even number of each. Whereas the non-square 55,125 is prime factored into [3,3,5,5,5,7,7], with an odd number of 5's.

Also, it may be reasonable to scale down your number by factoring out any square factor you find. You can have a pre-computed list of primes and(?) their squares waiting. Doing this could reduce the size of your test number, improve speed, etc. Every time you successfully reduce a number, you arrive at something smaller to test. Take the aforementioned 99,225 and 55,125. If you know that 3 goes into each, try to divide out 9. You get 11,025 and 6,125. Attempt to reduce by a factor 9 again and you get 1,225 and 6,125, respectively, and 9 wont go into either any more. Next try 5. Attempt to reduce by 25 and you get 49 and 245, respectively. So on. We need only test 49 and 245 for squareness. The former clearly is; the latter is not, because it can be divided by 5 once but not twice.

On a side note, once you factor out a value, it may be worthwhile to revisit some of the prior rules and tricks, as some of the patterns may emerge and reveal information.

Another tidbit is that all integers can be factored into its integer factors, including 1 and itself. If this list comprises of only unique factors then this rule applies. Non-perfect squares have an even number of factors because they come in pairs, one on either side of the square root. But perfect squares have an odd number of unique factors, since its square root is counted once. Unfortunately this test is a bit useless since it entails finding a list of factors which include the square root itself. Take the perfect square 9 for example. Its integer factors are [1,3,9]. The 3 is the square root, but there are an odd number of terms in the list. The non-square 10, however, has integer factors [1,2,5,10].

Answer 4

You can make the algorithm you link to $O(\log^2 n)$ by returning not only $\left\lfloor\sqrt n\right\rfloor$ but also $\left\lfloor\sqrt n\right\rfloor^2$. Then you only need additions in each of the $O(\log n)$ steps, which only take $O(\log n)$ time.

Answer 5

I think I have a partial answer. What I really wanted was an algorithm which decides squareness without examining all the input digits, the way the algorithm for evenness does (in base 10).

But I think there is no such algorithm. Suppose $s_i$ and $s_i'$ were numbers which, represented in base $r$, agree in all but their $i$th digit. An algorithm $\mathcal A$ which decided squareness for base-$r$ numerals would have to examine the $i$th digit of its input. Whether $\mathcal A$ examines the $i$th digit earlier or later makes no difference: examining it last means that $\mathcal A$ has examined its entire input, and examining it earlier provides no information in distinguishing $s_i$ and $s_i'$.

So I think if I can show that $s_i$ and $s_i'$ actually exist for all choices of $r$ and $i$, I will be done. I need $s_i$ square and $s_i'$ not square, and $|s_i - s_i'| = kr^i $ for some $k$. But (waving hands) this is extremely easy to accomplish because there are so many possible choices of $s_i'$.

I should check to make sure that the argument fails to go through when $\mathcal A$ is checking for divisibility by $d$ rather than squareness. But it does fail to go through: I need $m_i$, a multiple of $k$ and $m_i'$, not a multiple of $k$, where $|m_i - m_i'| = kr^i$ for some $k$. But if $d|r$, there is no such $m_i$ and $m_i'$ unless $i=0$, and indeed the $o$th digit is the only one we must examine.

This still leaves open whether there is an algorithm significantly better than $O(\log^2 n)$, even though it must examine the entire input. But it rules out an algorithm that is better than $O(\log n)$.

Answer 6

I don't know if this is related to what you guys are posting about but here it goes:

When you used the traditional way of finding a square root (you know the one in which you find the largest 2ddy times y that can fit in a number r that is created by doing a previous similar operation and then appending the next two digits of the number you are trying to find the square root of. If the number you are trying to find the square root of is irrational, this can go on forever. Otherwise, it ends after a finite number of steps. y is a digit from 0 to 9. dd is the group of digits so far acquired in the square root operation while 2dd is dd times 2.

Example:

Finding the square root of 1089:

0..10; 10 03 x 3 = 9; 10 - 9 = 1; 1..89; 189

3 x 2 = 6; 63 x 3 = 189; 189 - 189 = 0 done

The square root of 1089 is 33

Now to find new perfect square, you find a square root of a number that is not a perfect square like say 24500

0..02; 2; 01 x 1 = 1; 2 - 1 = 1; 1..45; 145 1 x 2 = 2; 25 x 5 = 125; 145 - 125 = 20; 20..00; 2000; 15 x 2 = 30; 306 x 6 = 1836; 2000 - 1836 = 164; final remainder equals 164

This means that 24500 is 164 more than a perfect square which is:

24500 - 164 = 24336 whose square root is 1..5..6; 156 the same first three digits that were found when calculating the square root of 24500.

If you would have made a mistake in the final step for the third digit like the following:

305 x 5 = 1525; 2000 - 1525 = 475; 24500 - 475 = 24025

You would have ended up finding the previous perfect square 24025; square of 155