Mi pregunta es la siguiente:
Hay un polytime no numéricos algoritmo para el cálculo de la raíz cuadrada de cuadrado perfecto enteros?
El más elemental es el algoritmo, el mejor!
EDITAR: Esta es probablemente la más tonta la pregunta que me has pedido alguna vez (espero!). Como se ha señalado por picakhu, desde la entrada de número entero $n$ es cuadrado perfecto, podemos simplemente hacer una búsqueda binaria para encontrar el número cuyo cuadrado es igual a $n$.
