Why is std::pow(int, int) way faster than for loop with integer values?

Question

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

P = abⁿ + a²b^n-1 + a³b^n-2 + ... aⁿb

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.

Answer 1

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

• Why does pow(5,2) become 24?
• Why pow(10,5) = 9,999 in C++

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 b¹⁰⁰⁰⁰⁰ 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