0
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Of course there is an algorithm: How would you solve the problem yourself with an infinite supply or paper and pencils? $\endgroup$ – Jeffε Jan 11 '12 at 10:24
  • 1
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Jan 13 '12 at 12:30
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does finding square root have $NC$ algorithm? $\endgroup$ – T.... Aug 19 '17 at 8:23
  • $\begingroup$ In particular is testing perfect square in $NC$? $\endgroup$ – T.... Aug 19 '17 at 8:30
  • 1
    $\begingroup$ I'm not in the office to check it, but it is very likely mentioned in the paper by Hesse, Allender, and Barrington where they prove that division and iterated multiplication are uniform TC^0. $\endgroup$ – Emil Jeřábek Aug 19 '17 at 11:00
  • 1
    $\begingroup$ 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 ... $\endgroup$ – Emil Jeřábek Aug 25 '17 at 13:49
  • 1
    $\begingroup$ ... 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 . $\endgroup$ – Emil Jeřábek Aug 25 '17 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.