# 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? Commented Apr 21, 2011 at 4:51
• No idea if this is relevant, but you could do a binary search Commented Apr 21, 2011 at 4:53
• Did you peruse the results of Googling "fast integer square root"? Commented Apr 21, 2011 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
Commented Apr 21, 2011 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. Commented Apr 21, 2011 at 4:57

## 1 Answer

The following should suffice, from Cohen: A course in computational algebraic number theory.

• I thought of some "computer algebra" algorithms like this myself. But when the given integer is perfect square, I think binary search will work!
– Dai
Commented Apr 21, 2011 at 5:05
• See this Python shifting algorithm with good starting over estimate. Recognizing what 'should suffice' and pasting it into an answer is worth a (+1) . Commented Jul 27, 2021 at 13:01