11
$\begingroup$

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

$\endgroup$
10
  • 3
    $\begingroup$ What's a non-numerical algorithm? And by "computing", do you mean "iteratively approximating by rational numbers"? If not, what do you mean? $\endgroup$
    – joriki
    Commented Apr 21, 2011 at 4:51
  • 5
    $\begingroup$ No idea if this is relevant, but you could do a binary search $\endgroup$
    – picakhu
    Commented Apr 21, 2011 at 4:53
  • $\begingroup$ Did you peruse the results of Googling "fast integer square root"? $\endgroup$ Commented Apr 21, 2011 at 4:57
  • 1
    $\begingroup$ @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? $\endgroup$
    – Dai
    Commented Apr 21, 2011 at 4:57
  • 1
    $\begingroup$ I can imagine an $O(\sqrt n)$ time algorithm -- checking every number from 0 until you reach one that squares to your number. $\endgroup$
    – Justin L.
    Commented Apr 21, 2011 at 4:57

1 Answer 1

11
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .