calgorithmmathexponentiation

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

What is the most efficient way given to raise an integer to the power of another integer in C?

// 2^3
pow(2,3) == 8

// 5^5
pow(5,5) == 3125
Solution

  • 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.