# Complexity of finding the square root of a perfect square

What is the complexity of precisely finding the square root of a perfect square?

• Of course there is an algorithm: How would you solve the problem yourself with an infinite supply or paper and pencils? Jan 11, 2012 at 10:24
• I removed the part of the question which asks whether there is an algorithm to compute the square root of a perfect square at all, because that part is too elementary for this website. Please read How to ask a good question and in particular Understand what you really want to ask. Jan 13, 2012 at 12:30

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.
• Does finding square root have $NC$ algorithm? Aug 19, 2017 at 8:23
• In particular is testing perfect square in $NC$? Aug 19, 2017 at 8:30
• I can’t say I understand what you wrote. Linear programs don’t have any notion of “input” separate from the program itself. The P-completeness of LP means that there is a (easily computable) function $L(a,b)$ that gives a linear program such that $L(a,b)$ is feasible iff there is a perfect square in $[a,b]$. I likewise don’t know why would you think you only need logarithmic number of variables. The construction of $L(a,b)$ that I know makes the number of variables the size of a circuit that computes the original problem, which will be ... Aug 25, 2017 at 13:49
• ... polynomial in the size of the original input $a,b$. Concerning your last question, I’m sorry, but I am busy, and not interested in answering elementary questions by email. You should ask your tutor. Or at cs.stackexchange.com . Aug 25, 2017 at 13:51