# Algorithm for computing square root of a perfect square integer?

My question is the following:

Is there a polytime non-numerical algorithm for computing square root of perfect square integers?

The more elementary the algorithm is, the better!

EDIT: This is probably the most silly question I ever asked (I hope!). As pointed out by picakhu, since the input integer $n$ is perfect square, we can simply do a binary search to find the number whose square equals to $n$.

-
What's a non-numerical algorithm? And by "computing", do you mean "iteratively approximating by rational numbers"? If not, what do you mean? –  joriki Apr 21 '11 at 4:51
No idea if this is relevant, but you could do a binary search –  picakhu Apr 21 '11 at 4:53
Did you peruse the results of Googling "fast integer square root"? –  Bill Dubuque Apr 21 '11 at 4:57
@Joriki: Numerical are algorithms that use numerical approximation (as opposed to general symbolic manipulations). So I prefer symbolic manipulation. But picakhu's answer sounds right! That's clever! It's a shame that I didn't think of that. Picakhu, could you please make it an answer? –  Dai Apr 21 '11 at 4:57
I can imagine an $O(\sqrt n)$ time algorithm -- checking every number from 0 until you reach one that squares to your number. –  Justin L. Apr 21 '11 at 4:57