# 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

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

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

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 thought this was the math forum, not the programming forum. Who cares about algorithms and run times? Im only providing information that hasnt already been explicitly laid out. And I made it perfectly clear at the beginning that none of these verify squareness, but by using them you dont waste your time on more complicated algorithms that would only turn up the same result. It doesnt matter how efficient those algorithm are, they are not more simple than these basic tests. I fail to see why you have to criticize my contribution. –  CogitoErgoCogitoSum Mar 15 '14 at 3:54
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