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

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 3

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