Why Is Pow(Int, Int) So Slow

Why is pow(int, int) so slow?

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.

Why is Math.pow(int,int) slower than my naive implementation?

As others have said, you cannot just ignore the use of double, as floating point arithmetic will almost certainly be slower. However, this is not the only reason - if you change your implementation to use them, it is still faster.

This is because of two things: the first is that 2^2 (exponent, not xor) is a very quick calculation to perform, so your algorithm is fine to use for that - try using two values from Random#nextInt (or nextDouble) and you'll see that Math#pow is actually much quicker.

The other reason is that calling native methods has overhead, which is actually meaningful here, because 2^2 is so quick to calculate, and you are calling Math#pow so many times. See What makes JNI calls slow? for more on this.

Why is the pow function slower than simple operations?

pow(double,double) needs to handle raising to any power, not just an integer based power, or especially 2. As such, it's far more complicated than just doing a simple multiplication of two double values.

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

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

Replacing extrordinarily slow pow() function

Just write your own pow function, put the .o file in a static library archive libmypow.a somewhere in the linker's library path, and pass -lmypow when linking.

The most efficient way to implement an integer based power function pow(int, int)

Exponentiation by squaring.

int ipow(int base, int exp)
{
    int result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}

This is the standard method for doing modular exponentiation for huge numbers in asymmetric cryptography.

---

Related Topics