Why is pow(int, int) so slow?

Fang picture Fang · Dec 10, 2016 · Viewed 9k times · Source

I've been working on a few project Euler exercises to improve my knowledge of C++.

I've written the following function:

int a = 0,b = 0,c = 0;

for (a = 1; a <= SUMTOTAL; a++)
{
    for (b = a+1; b <= SUMTOTAL-a; b++)
    {
        c = SUMTOTAL-(a+b);

        if (c == sqrt(pow(a,2)+pow(b,2)) && b < c)
        {
            std::cout << "a: " << a << " b: " << b << " c: "<< c << std::endl;
            std::cout << a * b * c << std::endl;
        }
    }
}

This computes in 17 milliseconds.

However, if I change the line

if (c == sqrt(pow(a,2)+pow(b,2)) && b < c)

to

if (c == sqrt((a*a)+(b*b)) && b < c)

the computation takes place in 2 milliseconds. Is there some obvious implementation detail of pow(int, int) that I'm missing which makes the first expression compute so much slower?

Answer

e2-e4 picture e2-e4 · Dec 10, 2016

pow() works with real floating-point numbers and uses under the hood the formula

pow(x,y) = e^(y log(x))

to calculate x^y. The int are converted to double before calling pow. (log is the natural logarithm, e-based)

x^2 using pow() is therefore slower than x*x.

Edit based on relevant comments

  • Using pow even with integer exponents may yield incorrect results (PaulMcKenzie)
  • In addition to using a math function with double type, pow is a function call (while x*x isn't) (jtbandes)
  • Many modern compilers will in fact optimize out pow with constant integer arguments, but this should not be relied upon.