8

Is it more efficient to do multiplication than raise to power 2 in c++?

I am trying to do final detailed optimizations. Will the compiler treat x*x the same as pow(x,2)? If I remember correctly, multiplication was better for some reason, but maybe it does not matter in c++11.

Thanks

5
  • Depends on whether the optimizer (or function's implementation possibly) takes care of it. Look at the produced assembly or benchmark it.
    – chris
    May 23, 2013 at 20:42
  • I imagine x << 1 is what is actually happening. May 23, 2013 at 20:43
  • 9
    x^2 is not raise to power 2!
    – Lol4t0
    May 23, 2013 at 20:43
  • 2
    I certainly hope the compiler won't treat x*x the same as x^2 because ^ is XOR not pow.
    – syam
    May 23, 2013 at 20:44
  • ah yes sorry, I meant pow instead of ^ May 23, 2013 at 20:45

8 Answers 8

20

If you're comparing multiplication with the pow() standard library function then yes, multiplication is definitely faster.

0
6

I general, you should not worry about pico-optimizations like that unless you have evidence that there is a hot-spot (i.e. unless you've profiled your code under realistic scenarios and have identified a particular chunk of code. Also keep in mind that your clever tricks may actually cause performance regressions in new processors where your assumptions will no longer hold.

Algorithmic changes are where you will get the most bang for your computing buck. Focus on that.

Tinkering with multiplications and doing clever bit-hackery... eh not so much bang there* Because the current generation of optimizing compilers is really quite excellent at their job. That's not to say they can't be beat. They can, but not easily and probably only by a few people like Agner Fog.

* there are, of course, exceptions.

8
  • 1
    +1 for "They can, but not easily and probably only by a few people like Agner Fog." Ain't that the truth! May 24, 2013 at 17:43
  • 1
    Interestingly enough, the difference between pow() and multiplication actually IS an algorithmic difference. ;) Consider if the OP asked the same thing with a different example and wording: "pow(x, 8) expresses my intent more clearly than xxxxxxxx. Is multiplication faster?" You might call it a pico-optimization, but going from pow() to multiplication is technically an algorithmic (+ constant) improvement. (...and compared to naive sequential multiplication, "x2 = xx; x4 = x2*x2; answer = x4*x4;" is also a handcoded expansion of an algorithmically improved integer power function.)
    – Mike S
    May 30, 2013 at 14:12
  • 1
    I don't disagree with you; as a matter of fact, I think we agree conceptually but approach the issue from slightly different angles. I certainly think that one should try to write efficient code to begin with, and that means learning what does and doesn't make a difference in that context. But that's quite different from micro-optimizing as you go. Jun 5, 2013 at 17:38
  • 2
    Also beware blind faith in compilers: Even ten years ago, most people assumed compilers performed optimizations on a scale they still don't today. (At the micro-optimization level, instruction scheduling still benefits from reordering source code lines!) pow() is rarely replaced with integer intrinsics: Usually the full int->float->pow->int is done, and pow can't be optimized because fp math is not associative. Quick test: With GCC 4.8, pow(i, 2) is as fast as ii, but pow(i, 4) is 115 times slower than iiii. With Clang 3.3, it's 337 times slower, since it optimizes the multiplies better.
    – Mike S
    Jun 5, 2013 at 18:16
  • 2
    Just saw your comment: Micro-optimizing as you go is a brutally slow/unproductive way to code, especially if you get carried away and write unreadable bit-twiddling code (which probably won't help), or if you spend a lot of time reordering instructions to aid the scheduler, etc. It's never a good idea to write unreadable "optimizations" before profiling, but if you're deciding between two equally legible versions of idiomatic code spread across the codebase, investing early in the "habitual learning process" is probably wise...even if it means micro-optimization slog the first time around.
    – Mike S
    Jun 5, 2013 at 18:27
5

When it comes to performance, always make measurements to back up your assumptions. Never trust theory unless you have a benchmark that proves that theory right.

Also, keep in mind that x ^ 2 does not yield the square of 2 in C++:

#include <iostream>

int main()
{
    int x = 4;
    std::cout << (x ^ 2); // Prints 6
}

Live example.

2

The implementation of pow() typically involves logarithms, multiplication and expononentiaton, so it will DEFINITELY take longer than a simple multiplication. Most modern high end processors can do multiplication in a couple of clockcycles for integer values, and a dozen or so cycles for floating point multiply. exponentiation is either done as a complex (microcoded) instructions that takes a few dozen or more cycles, or as a series of multiplication and additions (typically with alternating positive and negative numbers, but not certainly). Exponentiation is a similar process.

On lower range processors (e.g. ARM or older x86 processors), the results are even worse. Hundreds of cycles in one floating point operation, or in some processors, even floating point calculations are a number of integer operations that perform the same steps as the float instructions on more advanced processors, so the time taken for pow() could be thousands of cycles, compared to a dozen or so for a multiplication.

Whichever choice is used, the whole calculation will be significantly longer than a simple multiplication.

The pow() function is useful when the exponent is either large, or not an integer. Even for relatively large exponents, you can do the calculation by squaring or cubing multiple times, and it will be faster than pow().

Of course, sometimes the compiler may be able to figure out what you want to do, and do it as a sequence of multiplications as a optimization. But I wouldn't rely on that.

Finally, as ALWAYS, for performance questions: If it's really important to your code, then measure it - your compiler may be smarter than you thin. If performance isn't important, then perform the calculation that is the makes the code most readable.

1

pow is a library function, not an operator. Unless the compiler is able to optimize out the call (which it legitimately do by taking advantage of its knowledge of the behavior of the standard library functions), calling pow() will impose the overhead of a function call and of all the extra stuff the pow() function has to do.

The second argument to pow() doesn't have to be an integer; for example pow(x, 1.0/3.0) will give you an approximation of the cube root of x. That's going to require some fairly sophisticated computations. It might fall back to repeated multiplication if the second argument is a small integral value, but then it has to check for that at run time.

If the number you want to square is an integer, pow will involve converting it to double, then converting the result back to an integer type, which is relatively expensive and could cause subtle rounding errors.

Using x * x is very likely to be faster and more reliable than pow(x, 2), and it's simpler. (In most contexts, simplicity and reliability are more important considerations than speed.)

0

C/C++ does not have a native "power" operator. ^ is the bitwise exclusive or (xor). Thus said, the pow function is probably what you are looking for.

Actually, for squaring an integer number, x*x is the most immediate way, and some compiler might optimize it to machine operation if available.

0

You should read the following link Why doesn't GCC optimize a*a*a*a*a*a to (a*a*a)*(a*a*a)?

pow(x,2) will most likely be converted to xx. However, higher powers such as pow(x,4) may not be done as optimally as possible. For example pow(x,4) could be done in 3 multiplications xxxx or in two (xx)(x*x) depending on how strict you require the floating point definition to be (by default I think it will use 3 multiplications.

It would be interesting to see what for example pow(x*x,2) produces with and without -ffast-math.

0

you should look into boost.math's pow function template. it takes the exponent as template parameter and automatically calculate, for example, pow<4>(x) as (x*x)*(x*x).

http://www.boost.org/doc/libs/1_53_0/libs/math/doc/sf_and_dist/html/math_toolkit/special/powers/ct_pow.html

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.