<p>As mentioned in any number of basic sources (e.g., <a href="https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations" rel="noreferrer">Wikipedia</a>), <span class="math-container">$\lfloor\sqrt a\rfloor$</span> can be computed in time <span class="math-container">$O(M(n))$</span> using Newton iteration, where <span class="math-container">$n=\log a$</span> is the length of the input, and <span class="math-container">$M(n)$</span> is the complexity of <a href="https://en.wikipedia.org/wiki/Multiplication_algorithm" rel="noreferrer">multiplication</a> of <span class="math-container">$n$</span>-bit integers. The best currently known multiplication algorithm due to Harvey and Van der Hoeven achieves <span class="math-container">$M(n)=O(n\log n)$</span>.</p>
<p>The <span class="math-container">$O(M(n))$</span> bound is optimal for general integer <span class="math-container">$a$</span>: if <span class="math-container">$\lfloor\sqrt a\rfloor$</span> can be computed in time <span class="math-container">$T(n)$</span>, where <span class="math-container">$T(n)$</span> satisfies some mild regularity conditions, then integer multiplication can be computed in time <span class="math-container">$O(T(n))$</span>. This follows from <a href="https://cstheory.stackexchange.com/a/25750">this answer</a> of mine, and the observation that you can compute an <span class="math-container">$n$</span>-bit approximation of <span class="math-container">$\sqrt x$</span> for a dyadic rational <span class="math-container">$x\in[0,1]$</span> in time <span class="math-container">$O(T(n))$</span> using <span class="math-container">$2^{-n}\lfloor\sqrt{\lfloor2^nx\rfloor}\rfloor$</span>.</p>
<p>However, no superlinear lower bound for multiplication is known.</p>
<p>I do not know whether the bound is optimal under the promise that <span class="math-container">$a$</span> is a perfect square, but I’m pretty sure that no algorithm better than <span class="math-container">$O(M(n))$</span> is known even in this case.</p>

CC BY-SA 4.0
2024-07-25T07:22:07.453Z
2024-07-25T07:22:07.453Z
Emil Jeřábek
<p>Given a square number in <span class="math-container">$n$</span> bits can we compute its square root in <span class="math-container">$O(n)$</span> time?</p>
<p>In general can we compute <span class="math-container">$\lfloor\sqrt{a}\rfloor$</span> in <span class="math-container">$O(\log a)$</span> time?</p>

<ds.algorithms><time-complexity><nt.number-theory>
Time complexity of square root floor
Turbo
# Time complexity of square root floor

(Asked by: username_0 on 2024-07-24)

Given a square number in $n$ bits can we compute its square root in $O(n)$ time?

In general can we compute $\lfloor\sqrt{a}\rfloor$ in $O(\log a)$ time?

**Tags:** ds.algorithms, time-complexity, nt.number-theory


---

## 1 answers

### Answer by username_1 on 2024-07-25. Score: 5 | Accepted answer

As mentioned in any number of basic sources (e.g., [Wikipedia](https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations)), $\lfloor\sqrt a\rfloor$ can be computed in time $O(M(n))$ using Newton iteration, where $n=\log a$ is the length of the input, and $M(n)$ is the complexity of [multiplication](https://en.wikipedia.org/wiki/Multiplication_algorithm) of $n$-bit integers. The best currently known multiplication algorithm due to Harvey and Van der Hoeven achieves $M(n)=O(n\log n)$.

The $O(M(n))$ bound is optimal for general integer $a$: if $\lfloor\sqrt a\rfloor$ can be computed in time $T(n)$, where $T(n)$ satisfies some mild regularity conditions, then integer multiplication can be computed in time $O(T(n))$. This follows from [this answer](https://cstheory.stackexchange.com/a/25750) of mine, and the observation that you can compute an $n$-bit approximation of $\sqrt x$ for a dyadic rational $x\in[0,1]$ in time $O(T(n))$ using $2^{-n}\lfloor\sqrt{\lfloor2^nx\rfloor}\rfloor$.

However, no superlinear lower bound for multiplication is known.

I do not know whether the bound is optimal under the promise that $a$ is a perfect square, but I’m pretty sure that no algorithm better than $O(M(n))$ is known even in this case.


---

