C++ Math Operations – Correct Way to Raise an Integer to a Positive Power

c++mathnumerical

We know that for various reasons, there is no standard integer power function in C++. I'm performing exact arithmetic with rather small integers, what is the correct way to compute powers?

Best Answer

The standard, fast exponentiation uses repeated squaring:

uint_t power(uint_t base, uint_t exponent)
{
    uint_t result = 1;

    for (uint_t term = base; exponent != 0; term = term * term)
    {
        if (exponent % 2 != 0) { result *= term; }
        exponent /= 2;
    }

    return result;
}

The number of steps is logarithmic in the value of exponent. This algorithm can trivially be extended to modular exponentiation.

Update: Here is a modified version of the algorithm that performs one less multiplication and handles a few trivial cases more efficiently. Moreover, if you know that the exponent is never zero and the base never zero or one, you could even remove the initial checks:

uint_t power_modified(uint_t base, uint_t exponent)
{
    if (exponent == 0) { return 1;    }
    if (base < 2)      { return base; }

    uint_t result = 1;

    for (uint_t term = base; ; term = term * term)
    { 
        if (exponent % 2 != 0) { result *= term; }
        exponent /= 2;
        if (exponent == 0)     { break; }
    }

    return result;
}

Related Solutions

C++ – Function to Raise a Number to a Power

pow() in the cmath library. More info here. Don't forget to put #include<cmath> at the top of the file.

C++ Math – Raising a Number to a Huge Exponent Efficiently

Take advantage of property of modular arithmetic

(a × b) modulo M == ((a module M) × (b modulo M)) modulo M

By using above multiplication rule

(a^n) modulo M 
= (a × a × a × a ... × a) modulo M 
= ((a module M) × (a modulo M) × (a modulo M) ... × (a modulo M)) modulo M

Calculate the result by divide and conquer approach. The recurrence relation will be:

f(x, n) = 0                     if n == 0

f(x, n) = (f(x, n / 2))^2       if n is even
f(x, n) = (f(x, n / 2))^2 * x   if n is odd

Here is the C++ implementation:

int powerUtil(int base, int exp, int mod) {
    if(exp == 0) return 1;
    int ret = powerUtil(base, exp / 2, mod) % mod;
    ret = 1LL * ret * ret % mod;
    if(exp & 1) {
        ret = 1LL * ret * base % mod;
    }
    return ret;
}

double power(int base, int exp, int mod) {
    if(exp < 0) {
        if(base == 0) return DBL_MAX; // undefined
        return 1 / (double) powerUtil(base, -exp, mod);
    }
    return powerUtil(base, exp, mod);
}

Best Answer

Related Solutions

C++ – Function to Raise a Number to a Power

C++ Math – Raising a Number to a Huge Exponent Efficiently

Related Question