<p>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 <a href="http://en.wikipedia.org/wiki/Methods_of_computing_square_roots">http://en.wikipedia.org/wiki/Methods_of_computing_square_roots</a> for more square root algorithms, and <a href="http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations">http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations</a> for an overview of computational complexity of arithmetical operations.</p>

CC BY-SA 3.0
2017-08-19T08:23:17.663Z
Does finding square root have $NC$ algorithm?
Turbo
CC BY-SA 3.0
2017-08-19T08:30:31.963Z
In particular is testing perfect square in $NC$?
Turbo
CC BY-SA 3.0
2017-08-19T08:41:36.620Z
Yes, square roots can be in fact computed in uniform $\mathrm{TC}^0$.
Emil Jeřábek
CC BY-SA 3.0
2017-08-19T08:45:09.620Z
is this the reference (https://pdfs.semanticscholar.org/5f8b/d44c0a27627be872b912e5b526deea0f9b95.pdf)?
Turbo
CC BY-SA 3.0
2017-08-19T08:50:48.780Z
I'm not interested in downloading pdfs from random URLs. What is the author and title of the paper that you are asking about?
Emil Jeřábek
CC BY-SA 3.0
2017-08-19T08:51:53.143Z
I should have said 'is this a good reference?'. I am wondering if there is a good reference.
Turbo
CC BY-SA 3.0
2017-08-19T11:00:09.073Z
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.
Emil Jeřábek
CC BY-SA 3.0
2017-08-19T11:31:38.197Z
I looked there I am unable to find the result you mention there.
Turbo
CC BY-SA 3.0
2017-08-21T14:22:34.873Z
It’s the last item in Corollary 6.5.
Emil Jeřábek
CC BY-SA 3.0
2017-08-21T15:53:21.737Z
May I ask if 'Given 0<a<b find a perfect square in [a,b]' is also in TC0 (would that be functional version of TC0?)?
Turbo
CC BY-SA 3.0
2017-08-21T16:00:05.390Z
Yes, this is also in $\mathrm{TC}^0$ (or more precisely, $\mathrm{FTC}^0$): “output $\lfloor\sqrt b\rfloor^2$ if it is $\ge a$, otherwise there is no solution”.
Emil Jeřábek
CC BY-SA 3.0
2017-08-21T16:14:29.100Z
P consists of decision problems. Linear programming (in the form relevant here) is a decision problem. Any problem in P reduces to linear programming, that means decision problems. Computing perfect squares in $[a,b]$ is a search problem, not a decision problem, so the reduction to linear programming does not apply. (I have no idea how any of this has anything to do with NC or TC0.)
Emil Jeřábek
CC BY-SA 3.0
2017-08-23T22:00:33.183Z
So there is a linear program $L(a,b)$ that depends only on $a,b$ that outputs $1$ iff input integer $c$ is in $[a,b]$ and is a perfect square? Since the testing squares and testing membership in $[a,b]$ are in $TC0$ can we expect only logarithmic number of variables and constraints in the linear program and so this particular linear program can be solved in $TC0$. I have some further queries which can I email you?
Turbo
CC BY-SA 3.0
2017-08-25T13:49:22.057Z
I can’t say I understand what you wrote. [Linear programs](https://en.wikipedia.org/wiki/Linear_programming) 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 ...
Emil Jeřábek
CC BY-SA 3.0
2017-08-25T13:51:50.153Z
... 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 http://cs.stackexchange.com .
Emil Jeřábek
CC BY-SA 3.0
2017-08-25T16:23:43.340Z
thank you...,... $TC0$ is in $L$ that is why I thought. Actually I do not have any further queries along this line since I was thinking something else.
Turbo
CC BY-SA 4.0
2022-07-30T16:18:51.233Z
Given, a perfect square, I think the binary search algorithm is sufficient to determine the square root. This has time complexity of $\mathcal{O}{(log\ n)}$
Joker
CC BY-SA 4.0
2022-07-30T16:59:14.860Z
@Joker First, $n$ is not the input number itself, but the number of its digits. Thus binary search takes $O(n)$ multiplications rather than $O(\log n)$. Second, each of these multiplications takes about $M(n)$ steps, rather than $O(1)$ as you seem to assume. Thus, the binary search algorithm takes $O(M(n)n)$ steps, which is much worse than other methods.
Emil Jeřábek
CC BY-SA 4.0
2022-07-30T17:06:01.313Z
For the record, if you count the number of multiplications instead of the full complexity, Newton iteration is still much more efficient than binary search, as it takes $O(\log n)$ multiplications, whereas binary search takes $O(n)$, as already mentioned.
Emil Jeřábek
CC BY-SA 3.0
2012-01-11T12:13:59.450Z
2012-01-12T17:08:40.757Z
2012-01-12T17:08:40.757Z
Emil Jeřábek
<p>What is the complexity of precisely finding the square root of a perfect square?</p>

CC BY-SA 3.0
2012-01-11T10:24:17.620Z
Of course there is an algorithm: How would you solve the problem yourself with an infinite supply or paper and pencils?
Jeffε
CC BY-SA 3.0
2012-01-13T12:30:00.610Z
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](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question) and in particular [Understand what you really want to ask](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/307#307).
Tsuyoshi Ito
<cc.complexity-theory><ds.algorithms>
Complexity of finding the square root of a perfect square
Timothy Zacchari
# Complexity of finding the square root of a perfect square

(Asked by: username_0 on 2012-01-11)

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

**Tags:** cc.complexity-theory, ds.algorithms

> **Comments:**
> **username_1**: Of course there is an algorithm: How would you solve the problem yourself with an infinite supply or paper and pencils?  
> **username_2**: 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](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question) and in particular [Understand what you really want to ask](http://meta.cstheory.stackexchange.com/questions/300/how-to-ask-a-good-question/307#307).  

---

## 1 answers

### Answer by username_3 on 2012-01-11. Score: 10

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.

> **Comments:**
> **username_4**: Does finding square root have $NC$ algorithm?  
> **username_4**: In particular is testing perfect square in $NC$?  
> **username_3**: Yes, square roots can be in fact computed in uniform $\mathrm{TC}^0$.  
> **username_4**: is this the reference (https://pdfs.semanticscholar.org/5f8b/d44c0a27627be872b912e5b526deea0f9b95.pdf)?  
> **username_3**: I'm not interested in downloading pdfs from random URLs. What is the author and title of the paper that you are asking about?  
> **username_4**: I should have said 'is this a good reference?'. I am wondering if there is a good reference.  
> **username_3**: 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.  
> **username_4**: I looked there I am unable to find the result you mention there.  
> **username_3**: It’s the last item in Corollary 6.5.  
> **username_4**: May I ask if 'Given 0<a<b find a perfect square in [a,b]' is also in TC0 (would that be functional version of TC0?)?  
> **username_3**: Yes, this is also in $\mathrm{TC}^0$ (or more precisely, $\mathrm{FTC}^0$): “output $\lfloor\sqrt b\rfloor^2$ if it is $\ge a$, otherwise there is no solution”.  
> **username_3**: P consists of decision problems. Linear programming (in the form relevant here) is a decision problem. Any problem in P reduces to linear programming, that means decision problems. Computing perfect squares in $[a,b]$ is a search problem, not a decision problem, so the reduction to linear programming does not apply. (I have no idea how any of this has anything to do with NC or TC0.)  
> **username_4**: So there is a linear program $L(a,b)$ that depends only on $a,b$ that outputs $1$ iff input integer $c$ is in $[a,b]$ and is a perfect square? Since the testing squares and testing membership in $[a,b]$ are in $TC0$ can we expect only logarithmic number of variables and constraints in the linear program and so this particular linear program can be solved in $TC0$. I have some further queries which can I email you?  
> **username_3**: I can’t say I understand what you wrote. [Linear programs](https://en.wikipedia.org/wiki/Linear_programming) 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 ...  
> **username_3**: ... 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 http://cs.stackexchange.com .  
> **username_4**: thank you...,... $TC0$ is in $L$ that is why I thought. Actually I do not have any further queries along this line since I was thinking something else.  
> **username_5**: Given, a perfect square, I think the binary search algorithm is sufficient to determine the square root. This has time complexity of $\mathcal{O}{(log\ n)}$  
> **username_3**: @username_5 First, $n$ is not the input number itself, but the number of its digits. Thus binary search takes $O(n)$ multiplications rather than $O(\log n)$. Second, each of these multiplications takes about $M(n)$ steps, rather than $O(1)$ as you seem to assume. Thus, the binary search algorithm takes $O(M(n)n)$ steps, which is much worse than other methods.  
> **username_3**: For the record, if you count the number of multiplications instead of the full complexity, Newton iteration is still much more efficient than binary search, as it takes $O(\log n)$ multiplications, whereas binary search takes $O(n)$, as already mentioned.  

---

