2
$\begingroup$

What is the complexity (in flops, floating-point operations) of taking the $l_2$-norm of vector $\mathbf{v}\in\mathbb{R}^n$ (or $\mathbf{v}\in\mathbb{C}^n$ if a difference exists).

We have the following definition of the $l_2$-norm of $\mathbf{v}$:

$$ \lVert\mathbf{v}\rVert_2= \sqrt{|v_1|^2+\dots+|v_n|^2} $$

where $|v_i|$ is the absolute value of $v_i$ (or complex modulus if $v_i$ complex).

I guess that what bothers me the most is the square-root computation. I found that the square-root is considered one flop, and hence the complexity is $2n$ flops.

Isn't that wrong since the square-root should take more time to compute?

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ Side note: these days multiplication-addition pairs are fused into FMA's, so depending on what your goal is here, it might be $n+1$ flops for the whole formula. $\endgroup$ – Kirill Apr 23 '18 at 1:13
  • 1
    $\begingroup$ I think many computer scientists reserve "complexity" to mean something a different than flop counting (though both are important). Complexity is about describing the asymptotic behavior of the time (or memory, etc) in terms of the size of an arbitrarily large input. Here, only the time for the summation is sensitive to n. Even if computing a square root is slower than an add/multiply (certainly is), the time to perform just one of them is insensitive to n and has no contribution to the "complexity" for large n (in the CS-theory sense of the word). $\endgroup$ – rchilton1980 Apr 23 '18 at 14:44
  • $\begingroup$ @rchilton1980 relevant point. $\endgroup$ – Learn_and_Share Apr 23 '18 at 14:48
4
$\begingroup$

The square root is counted as a single floating point operation in the IEEE 754-2008 standard although that does not mean that it takes the same time as other operations. On Intel Xeon processors, the latency (the number of cycles an instruction takes to complete) of a square root might be between 5 to 7 times longer than a sum or a multiplication. You can check this out by comparing the latency reports for the instructions FADD, FMUL, and FSQRT in the Intel Xeon Scalable Processor throughput latency document.

The above assumes that you are implementing the $\ell^2$ norm in the most straight-forward way without using fused-multiply additions, vectorized operations, etc.

| cite | improve this answer | |
$\endgroup$

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.