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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
As mentioned in any number of basic sources (e.g., Wikipedia), $\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 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 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.
