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