7
$\begingroup$

Several sources state that the computational or time complexity of square rooting is the same as that of multiplication (or division). See for example:

  • Jean-Michel Muller, "Elementary Functions: Algorithms and Implementation" (Birkhäuser, Boston, USA, 2006, 2nd edn.) on p.93 where the Newton-Raphson method is considered. It is stated that "...the complexity of square root evaluation or division is the same as that of multiplication..."

  • H. Alt, "Square rooting is as difficult as multiplication", Computing, 1979, 21, (3), pp.221-232. It is stated on p.231 "...that we have shown that square rooting is of the same complexity as the other arithmetical operations mentioned. The proof can be extended to higher roots, as well."

Although there are several different approaches to implement computation of the elementary operations (+,-,x,/) it is therefore possible to implement square rooting such that the complexity is equivalent to an implementation of multiplication (a single multiplication of 2 real numbers).

What does "the proof can be extended to higher roots" mean? Is it possible to implement the calculation of the nth root with complexity equivalent to a single multiplication or to the multiplication of $n$ real numbers? If not, what is the complexity of calculating the nth root of a real number?

$\endgroup$
4
  • 2
    $\begingroup$ How are your real numbers represented? Without specifying this, it's rather unclear... $\endgroup$ Jun 13, 2012 at 10:04
  • $\begingroup$ Say single precision floating point real numbers $\endgroup$
    – aslan
    Jun 13, 2012 at 10:09
  • 1
    $\begingroup$ In the paper of H. Alt, big O notation is used, which is only an asymptotic complexity bound, and it does not mean that the operations are equivalent. In the analysis of high-level algorithms (the book of Jean-Michel Muller), the complexity of multiplication and square root evaluation is assumed the same for simplicity. In real computation, a square root evaluation is about 5 times more expensive than a multiplication. $\endgroup$
    – Stanislav
    Jun 13, 2012 at 10:17
  • 1
    $\begingroup$ If you are interested in the floating point instruction latencies in real processors, see "Intel 64 and IA-32 Architectures Optimization Reference Manual" (Appendix C) $\endgroup$
    – Stanislav
    Jun 13, 2012 at 10:20

2 Answers 2

12
$\begingroup$

First, note that the asymptotic complexity of arithmetic operations stated in the common literature concerns operations on numbers with arbitrary precision, and the running time is expressed as a function of the desired number of digits. From the standpoint of asymptotic complexity it makes no sense to ask for operations with constant precision (e.g., single floats, as you mentioned in the comments): there are only $O(1)$ such numbers, hence the operation can be evaluated in time $O(1)$ (e.g., by a look-up table).

Let me thus denote the desired precision as $m$ (since you use the customary $n$ for something else). The result you quote is that $\sqrt a$ can be computed in time $O(M(m))$, where $M(m)$ is any function (satisfying some mild regularity conditions) such that multiplication of two $m$-bit integers can be performed in time $M(m)$. (The currently known asymptotically fastest multiplication algorithm has $M(m)=m\log m\,2^{O(\log^*m)}$.) The algorithm uses Newton iteration $x\mapsto x-\frac{x^2-a}{2x}$. This iteration has a quadratic rate of convergence, hence $O(\log m)$ iterations suffice, and each step takes $O(1)$ multiplications and divisions, leading to the estimate $O(M(m)\log m)$ on the total running time. The extra factor of $\log m$ can be removed by the following observation: since the number of correct digits is roughly doubled by each iteration, we do not have to perform all operations with precision $m$, it suffices to use precision sufficient to accomodate the correct digits. Thus only the last iteration is performed with precision $m$, the last but one has precision $m/2$, the one before that $m/4$, and so on. Then the running time is $O(M(m)+M(m/2)+M(m/4)+\cdots)$. Since $M$ is essentially linear, this is can be bounded by a geometric series, whose sum is $O(M(m))$. (Note by the way that the fact that division can be done in time $O(M(m))$ also uses a similar Newton iteration argument.)

Now, what about $n$th roots in general? You can use Newton iteration again, as Denis suggests. The analysis is similar to the square root case, but since each step takes $O(\log n)$ multiplications, you get a bound $O(M(m)\log n)$. Note that if $n$ is given in binary, $\log n$ is the length of the input, hence this is an algorithm with worse than a quadratic running time. Another approach is to compute $\sqrt[n]a$ as $\exp((\log a)/n)$. Using binary splitting, the Taylor series for $\exp$ and $\log$ can be evaluated in time $O(M(m)(\log m)^2)$; using algorithms based on the arithmetic-geometric mean this can be reduced to $O(M(m)\log m)$, leading to $n$th root computation with the same time bound. This also has an extra $\log$ factor, but it is independent of $n$. I don’t know how to compute $\sqrt[n]a$ in time $O(M(m))$, and I am somewhat skeptical that such a thing is known. It might well be that the comment in Alt’s paper is only intended to cover the case of constant $n$.

$\endgroup$
3
  • $\begingroup$ +1.but the $m$ in $M(m)$ is very annoying,could we get it's upper bound by the polynomial or the function to solve? $\endgroup$ Jul 31, 2014 at 22:06
  • 2
    $\begingroup$ I can't make heads or tails of your comment. Any bound has to involve $m$, as it is the length of the output, and the bound is already polynomial (almost linear) as given. $\endgroup$ Aug 1, 2014 at 9:41
  • $\begingroup$ okay,let me try to get it $\endgroup$ Aug 1, 2014 at 11:34
3
$\begingroup$

The Newton-Raphson algorithm uses, for computation of $A^{1/p}$, the sequence $u_0=A$, $u_{n+1}=u_n-\frac {u_n^p-A}{pu_n^{p-1}}$, whose speed of convergence , always quadratic, is essentially independent of $p$ (and $A$). So, mostly, it asks for $\ln p$ multiplications and 1 division at each step.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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