The fast power algorithm is designed to compute large exponentiations efficiently, reducing time complexity from O(b) to O(log b). This method is particularly useful when dealing with modular arithmetic, such as calculating a^b mod m.

Core Principle

The fundamental idea relies on binary representation of the exponent. For any integer b, we can express it in binary form. Each bit position corresponds to a power of two. If a bits set (1), we multiply the corresponding power of the base into our result.

Consider computing a^11:

1. Convert 11 to binary: 1011
2. Process each bit from least significant to most:
   • Bit 0 (1): Include a^1
   • Bit 1 (1): Include a^2
   • Bit 2 (0): Skip a^4
   • Bit 3 (1): Include a^8

This approach allows us to compute the result using only a few iterations instead of multiplying a by itself b times.

Implementation

long long fast_power(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

Alternative Recursive Approach

An alternative implementation uses recursion and divides the problem into subproblems:

long long recursive_power(long long base, long long exp, long long mod) {
    if (exp == 0) return 1;
    if (exp == 1) return base % mod;
    
    long long half = recursive_power(base, exp / 2, mod);
    long long square = (half * half) % mod;
    
    if (exp % 2 == 1) {
        return (square * base) % mod;
    }
    return square;
}

Application Example

When solving problems like finding 2^1000 mod 10^9 + 7, direct computation would be impractical. Instead, the fast power algorithm reduces the number of operations significantly. The key insight is to apply modular arithmetic at each step to prevent overflow.

For example, when computing large powers modulo a number:

1. Initialize result = 1
2. While exponent > 0:
   • If current bit is set, multiply result by current base (mod)
   • Square the base (mod)
   • Right shift exponent
3. Return result

This technique is essential for competitive programming problems involving modular exponentiation, especially when dealing with very large exponents.