# Detecting perfect squares faster than by extracting square root

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.

-
Addendum: While looking into this I found this interesting related paper, Derivation of a Fast Integer Square Root Algorithm, which derives a fast, simple algorithm from a constructive existence proof via the unusual induction principle $\left[P(0)\wedge (\forall n.P(\lfloor{n\over 4}\rfloor)\Rightarrow P(n))\right] \Rightarrow \forall n.P(n)$. – MJD Apr 13 '12 at 18:48
– leonbloy Apr 13 '12 at 19:19
@leonbloy Thanks very much for these interesting links. I am aware of the tactic of quickly deciding whether $n$ is a square by looking at its last digit and checking if it is an appropriate quadratic residue. But I don't think this can change the $O()$ of the algorithm, just its multiplicative constant. I was hoping to learn if there is some generalization of this technique that can reduce the asymptotic order of the algorithm. – MJD Apr 13 '12 at 19:38
@MarkDominus I strongly suspect not, too, and I think there's a subtlety in your initial comment that holds much of the reason why. For small constants $k$ you're correct that there's a $O(\log n)$ algorithm for deciding divisibility (incidentally, this usually gets written $O(n)$, reflecting the actual size of the input). But for dividing $n$-digit numbers by $k$-digit numbers where $k$ is proportional to $n$ instead of constant, divisibility takes something more like $O(n^2)$ time (technically, it takes as long as multiplication does, if you use a fast multiplication algorithm). – Steven Stadnicki Jun 20 '12 at 21:49

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 any odd prime, 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.

-
Regarding note [2], interestingly the predicted number of false positives for using 18 primes to test 1 billion integers is $(1/2)^{18}10^{9} \approx 3,800$. Why are actual results 3 orders of magnitude better than the theoretical? Something weird going on there... – jrodatus Jul 22 '15 at 21:55

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

-

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.

-
Thanks for this useful observation, but it is not really what I am looking for. I will try to edit the question appropriately. – MJD Apr 13 '12 at 15:56

Well, 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, all perfect squares end in the numbers 0, 1, 4, 5, 6, or 9. This is a necessary condition. 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,52 3 is obviously not a perfect square. See that? With this rule we've already eliminated two-fifth of all possible numbers.

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 for perfect squareness by testing just the 64.

The last two digits of a test number cannot both be odd. 34,833,8 73 is not a perfect square.

If the test number ends in a 1 or a 9, the number preceding it (not the digit, but the entirety of the number as a number unto itself) HAS to be a multiple of 4. Examples include 81, and the number 57,12 1 (because 5,712 is 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,0 7 4 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,8 4 6 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 33 1,62 5 is not a perfect square.

All perfect squares are equivalent to 0 or 1 (mod 3). That is, when divided by 3 there is always either a 0 or a 1 remainder. So if you get a 2, you don't have a perfect square.

All perfect squares are equivalent to 0 or 1 (mod 4). Similar to above. So if you get a remainder of 2 or 3 you know you don't have a perfect square. But just because you do get a 0 or a 1 does not mean you have a perfect square. For example, 236,194 is equivalent to 1 in mod 3, but in mod 4 it's equivalent to 2, and so it is not a perfect square. The number 13 is equivalent to 1 in both mod 3 and mod 4, but it is not a perfect square.

Dont waste your time on mod 4 test, though, when you can do a mod 8 instead. It provides you with the same, but more information. A perfect square must be equivalent to 0, 1, or 4 in mod 8. If you get a 1 then your root is odd, if 0 or 4 then the root is even (assuming there is a perfect square root). If 0, though, the root is a multiple of 4. If the remainder is 4 then the root is just even, not a multiple of 4.

This one takes some explanation. We are looking for what's called the "digital root". A digital root is the single-digit number you get when you add up all the digits of your test number. And add up all the digits of the sum you get. And add up all the digits of THAT sum. So on. Until you are left with only one digit. By the way, this is an equivalent test to mod 9 remainders. All perfect squares have a digital root of 1, 4, 7, or 9. If your digital root is 0, 2, 3, 5, 6 or 8 then it is not a perfect square. The number 56,430,143 is not a perfect square; I know because 5+6+4+3+0+1+4+3 = 26, and 2+6 = 8.

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.

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 complicated algorithms. These tests above use little more than comparison, conditionals, counting, and single-digit additions.

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.

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.

-
This is already covered in the original comments to the question - these tests can change some of the constants but any fixed finite number of these tests can't change the asymptotic time of the algorithm, since a positive fraction of all tested numbers will fail them. You could possibly build an algorithm by testing residues mod $f(n)$ distinct numbers, for some specific $f(n)$, but then the runtime of testing grows with $f(n)$ (obviously) and it would take much more careful analysis to determine both a suitable $f()$ and the runtime of the resulting algorithm. – Steven Stadnicki Mar 15 '14 at 3:41
I approach math from a pure, abstract approach. These are tests I would perform on paper if asked to determine squareness. Im not going to assume that anyone intent on answering this question for themselves also has a computer and is a skilled programmer. That is just absurd to me. Id like to provide the conceptual tools rather than the mechanical ones. – CogitoErgoCogitoSum Mar 15 '14 at 3:59
I criticize in this case not because I think the specific tests are impractical - they're clearly useful - but because they are specifically covered in the comments. OP has clearly indicated from the body of the question that they are interested in asymptotic runtimes (which is a question of mathematics and not programming) and indicates in comments that they're well aware of the residue tests, so I'm just not clear what this answer adds to the discussion. – Steven Stadnicki Mar 15 '14 at 4:09
Its called providing a concise list to satisfy the curiosity of anyone who might be interested in them. People come here to this question probably expecting to see these. The title of the question is how to detect, not find, square roots... and how to do it faster than by root extraction. The title of this question makes no reference to computers or algorithms, that is only in the body. People come here for the title question, and they expect to see answers similar to mine, and perhaps similar to others' as well. But certainly not exclusively about computers or algorithms. – CogitoErgoCogitoSum Apr 17 '14 at 15:35
@CogitoErgoCogitoSum — I think this answer is great!! Obviously it doesn't fully answer the question, but it does provide a wealth of practical information. I don't know who voted you down to –1. I voted you up a notch. – Todd Lehman Aug 3 '14 at 10:56

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

-
This isn't quite right, because it's possible that a better algorithm could conclude, after examining a few digits of $n$, that for some $i$ there is no $s_i$ and $s_i'$ with the desired properties that are consistent with the digits seen so far. I think the idea can still be made to work, but I need to think about it some more. – MJD Apr 14 '12 at 13:03
One surprising characteristic of this problem is that it matters what order the digits are presented to the algorithm! Usually, minor representational details, such as whether the numeral is written big-endian or little-endian, are unimportant. However, there is an $O(1)$ algorithm for deciding evenness of binary numbers when the input appears on the input tape least-bit first, but not when the input appears on the tape greatest-bit first. For questions of decidability, or membership in $\mathcal P$, bit order is unimportant, but for membership in $O(1)$ it is important! – MJD Apr 14 '12 at 13:49
Unless I made a mistake, I think the algorithm I gave in my answer below beats the log$^{2}$ time complexity by a big margin!! (Please let me know if I'm missing something.) – jrodatus Jul 13 '15 at 23:23

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

-