1

Me and my friend wrote a program which calculates the polynomial:

P = abn + a2bn-1 + a3bn-2 + ... anb

He used the C++ std::pow(int, int) function, whereas I used two for loops as I've been taught that for loops with integers are faster than the std::pow(int, int) function or in worst case the speed is gonna be almost the same!

His code:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int a = 1,b = 1,n = 100000;
    long long P = 0;

    for(int i = 1, j = n; i <= n; i++, j--)
    {
        P += pow(a,i) * pow(b,j);
    }
    cout << P;
    return 0;
}

The program returns 100000 as expected with execution time: 0.048 s and 0.049 s when ran second time

However when I run my code:

#include <iostream>

using namespace std;

int main()
{
    int a = 1,b = 1,n = 100000;
    long long P = 0;

    for(int i = 1, j = n; i <= n; i++, j--)
    {
        int c = a, d = b;

        for (int k = 1; k < i; ++k) {

            c *= a;
        }

        for (int k = 1; k < j; ++k) {

            d *= b;
        }

        P += c * d;
    }
    cout << P;
    return 0;
}

The program returns again the expected 100000 but with execution time: 17.039 s and 17.117 s when ran second time.

My question is, as I have always been taught by people and I have read in articles and tutorials that the std::pow(int, int) is either gonna be slower than a for loop with integers or the speed is gonna be almost equal, why is the execution time having such a big difference if we up the number to 1000000 it's gonna even take a couple of minutes before my code executes, whereas the pow(int, int) function code executes within seconds.

phuclv
  • 37,963
  • 15
  • 156
  • 475
ShadeyyWasTaken
  • 11
  • 2
  • 1
    What compiler did you use? What compile options did you use? – PaulMcKenzie Nov 20 '20 at 03:29
  • @PaulMcKenzie I used Code::Blocks 20.03 with the GNU GCC Compiler, all the others options are the default ones for the compiler – ShadeyyWasTaken Nov 20 '20 at 03:32
  • Code:Blocks is an IDE, not a compiler. What version of g++ is being used? Second, you need to know the compiler options, as that will determine if optimizations were used. A compiler's optimizer will blast away that loop you wrote, to be honest with you, [as shown here](https://godbolt.org/z/36xT78) – PaulMcKenzie Nov 20 '20 at 03:34
  • @PaulMcKenzie The version is g++ (MinGW.org GCC-6.3.0-1) 6.3.0 as I'm quite new to CS I don't know where to check the compiler options, I would be very grateful if you could help me so I can send you the options as well! – ShadeyyWasTaken Nov 20 '20 at 03:37
  • Go in the CodeBlocks settings and look for the compiler options. Second, look at the link I posted -- you see that the compiler knows how to optimize the loop, far more than your hand-coded `for` loop. You learn that compiler optimizers are amazing creatures. The compiler can easily determine how to inline those calls, use assembly tricks, etc. due to the nature of the original code, and not so with your version. – PaulMcKenzie Nov 20 '20 at 03:38
  • @PaulMcKenzie When I open the CodeBlocks global compiler settings it says that it is using GNU GCC Compiler and under the Compiler Settings, none of the compiler flags are checked, and the other compiler options, other resource compiler options and the #defines fields are blank. I hope these were the options you were asking for! From what I understood from your explanation the compiler is optimizing better the pow function than my for loops, resulting in better performance with the pow function, is that it? – ShadeyyWasTaken Nov 20 '20 at 03:48
  • The compiler could optimize the program of your friend and transformed the code to `int main() { cout << 100000; return 0; }` – 273K Nov 20 '20 at 03:50
  • The compiler would optimize your code also, if you had enabled optimizations. – 273K Nov 20 '20 at 03:52
  • 1
    @ShadeyyWasTaken -- Advice -- Go to the godbolt website and compare what your code does and what your friend's code does in terms of the assembly generated. Turn on the optimizations by specifying `-O2`. But the layman's reason why your friend's code is faster is because your friend placed the code in the compiler's hands by calling `std::pow`, and you are trying to beat the compiler at the optimization game by hand-coding a loop. In that contest, the compiler almost always wins. – PaulMcKenzie Nov 20 '20 at 03:55
  • Thank you for the explanations, now I understand! Your answers were very helpful! – ShadeyyWasTaken Nov 20 '20 at 04:06
  • Note that when `std::pow` is called with integer arguments, the arguments are converted to `double`. – eerorika Nov 20 '20 at 04:48
  • Your `for` loop to calculate powers is also a relatively naive approach, so its complexity is linear with the exponent. There are simple optimisations that can improve complexity so it is proportional to the log of the exponent. – Peter Nov 20 '20 at 05:21
  • Your code can be optimised by calculating the powers iteratively. For example `a^n = a^(n-1) * a` etc. – Damien Nov 20 '20 at 10:53

1 Answers1

4

It completely depends on the quality of std::pow implementation, and the optimization capability of your compiler

For example some standard libraries calculate pow(x, y) as exp(log(x)*y) even for integer exponents, therefor it may be inaccurate and slow, resulting in issues like these

But some better pow implementations check if the exponent is integer to use a better algorithm. They also use exponentiating by squaring so they'll be magnitudes faster than your linear multiplication like your for loop. For example for b100000 they need only 17 loops instead of 100000

If a compiler is smart enough to recognize your loop as to calculate power, it may convert to std::pow completely. But probably it's not your case so std::pow is still faster. If you write your pow(int, int) function that uses exponentiating by squaring then it may likely be faster than std::pow

phuclv
  • 37,963
  • 15
  • 156
  • 475