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

  • 0
    @Dai, Im $n$ot sure your condition on "non-numerical" even makes sense. The square root of a perfect square, n, is sqrt(n). Or, if you prefer, m is the square root of the perfect square m^2. That is as symbolic as you can get. If you have a real value to start, like 345,355,748, then any root will be numerical.2014-03-15

1 Answers 1

7

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

  • 0
    I thought of some "computer algebra" algorithms like this myself. But when the given integer is perfect square, I think binary search will work!2011-04-21