What Is Fast Exponentiation, and Why Use It?

Fast exponentiation, as the name suggests, computes the nth power of a value in drastically reduced time. While it may not see frequent use in early learning stages, the core logic behind its a fundamental concept worth mastering for any algorithm developer.

For example, to calculate (3^4), a brute force approach simply multiplies 3 four times to get 81. For small exponents this approach works fine, but brute force exponentiation has a time complexity of (O(n)), which becomes unacceptably slow when the exponent is very large. A typical modern processor can handle roughly (10^8) operations per second, so linear time quickly becomes a bottleneck, requiring a more efficient solution.

Core Idea of Fast Exponentiation

The algorithm is built on the basic exponent product rule: when multiplying exponents with the same base, the exponents add together. Take (3^{16}) as an example. We can rewrite this value as (3^8 \times 3^8). Once we know the value of (3^8), we get the final result with just one extra multiplication, instead of multiplying 3 eight more times. We can apply the same logic to split (3^8) into (3^4 \times 3^4), and keep splitting until we reach small, trivial exponents.

The full process to compute (3^{16}) becomes:

1. Calculate (3^2)
2. Square the result to get (3^4)
3. Square again to get (3^8)
4. Square a final time to get (3^{16})

Where brute force requires 15 multiplications for this result, fast exponentiation only needs 4. As the exponent grows larger, this performance gap widens dramatically. Fast exponentiation has a time complexity of (O(\log_2 n)), which is vastly more efficient than linear time for large values of n.

Extending to Arbitrary Exponents

The example above uses an exponent that is a power of two, but the approach can be easily adapted to work with any positive integer exponent. Any integer can be decomposed into a sum of powers of two, which is exactly what its binary representation represents.

Take exponent 34 as an example: 34 in binary is (100100_{(2)}), which equals (2^5 + 2^2). Applying the exponent product rule, (x^{34} = x^{32} \times x^{4}). We can compute each of these power-of-two terms with the splitting approach above, then multiply the results together to get the final answer. This works for any positive integer exponent.

Fast Exponentiation Implementations in C++

Recursive Implementation

This recursive approach breaks the problem into smaller subproblems following the splitting logic we covered:

// Compute base raised to the power exp
long long fast_pow_recursive(int base, int exp) {
    if (exp == 0) {
        // Any value to the 0 power is 1
        return 1;
    } else if (exp % 2 == 0) {
        long long half_power = fast_pow_recursive(base, exp / 2);
        return half_power * half_power;
    } else {
        long long half_power = fast_pow_recursive(base, (exp - 1) / 2);
        return base * half_power * half_power;
    }
}

Iterative Bitwise-Optimized Implementation

The iterative version below uses bitwise operations to improve performance, and is the most commonly used implementation of fast exponentiation:

// Iterative bitwise-optimized fast exponentiation
long long fast_pow(int base, int exp) {
    long long result = 1;
    while (exp) {
        // Check if current least significant bit is set (exp is odd)
        if (exp & 1) {
            result *= base;
        }
        // Square the base for the next bit position
        base *= base;
        // Shift exponent right to process the next bit
        exp >>= 1;
    }
    return result;
}

Matrix Fast Exponentiation

The exact same binary exponentiation approach used for scalar values can be applied to matrices, with only the multiplication operation needing to be redefined. Matrix exponentiation is an extremely useful tool for many problems, most notably accelerating dynamic programming computations.

The goal of matrix fast exponentiation is to compute a matrix raised to the nth power: [M^n = \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} \ a_{2,1} & a_{2,2} & a_{2,3} \ a_{3,1} & a_{3,2} & a_{3,3} \end{bmatrix}^n ]

A common C++ implementation uses a struct with an overloaded multiplication operator, as shown below for 2x2 matrices:

const int MOD = 1000000007;

struct Matrix {
    int data[5][5];
    Matrix() {
        memset(data, 0, sizeof(data));
    }
    Matrix operator*(const Matrix& other) const {
        Matrix res;
        // Loop order optimized for cache performance
        for (int i = 1; i <= 2; i++) {
            for (int k = 1; k <= 2; k++) {
                if (data[i][k] == 0) continue;
                for (int j = 1; j <= 2; j++) {
                    res.data[i][j] = (res.data[i][j] + data[i][k] * other.data[k][j]) % MOD;
                }
            }
        }
        return res;
    }
};

Matrix result, base_matrix;

Matrix fast exponentiation is most commonly used to speed up linear dynamic programming transitions, a technique known as matrix-accelerated dynamic programing.