# 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