Complexity of finding the square root of a perfect square What is the complexity of precisely finding the square root of a perfect square?
The square root of an $n$-digit number can be computed in time $O(M(n))$ using e.g. Newton’s iteration, where $M(n)$ is the time needed to multiply two $n$-digit integers. The current best bound on $M(n)$ is $n\log n\,2^{O(\log^*n)}$, provided by Fürer’s algorithm. See http://en.wikipedia.org/wiki/Methods_of_computing_square_roots for more square root algorithms, and http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations for an overview of computational complexity of arithmetical operations.