Fast Exponentiation

Fast Exponentiation

Algorithm Explanation

Fast exponentiation, also known as binary exponentiation, is an efficient algorithm to compute ab in O(log b) time. It works by repeatedly squaring the base and reducing the exponent by half at each step. If the exponent is odd, we multiply the result by the current base. This technique can be applied recursively or iteratively.

Algorithm Steps (Iterative)

  1. Initialize result = 1.
  2. While b > 0:
    • If b is odd, set result *= a.
    • Set a *= a.
    • Set b = b / 2 (integer division).

Time and Memory Complexity

  • Time Complexity: O(log b)
  • Space Complexity: O(1) for iterative version, O(log b) for recursive version

Easy Problems

1. Compute Power (ab)

Compute the value of ab using fast exponentiation.


#include <iostream>
using namespace std;

long long fastPower(long long a, long long b) {
    long long result = 1;
    while (b > 0) {
        if (b % 2 == 1)
            result *= a;
        a *= a;
        b /= 2;
    }
    return result;
}

int main() {
    cout << fastPower(2, 10) << endl; // Output: 1024
    return 0;
}

2. Power Modulo (ab % m)

Computes large powers under a modulus, commonly used in competitive programming and cryptography.


#include <iostream>
using namespace std;

long long modPower(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1)
            result = (result * a) % m;
        a = (a * a) % m;
        b /= 2;
    }
    return result;
}

int main() {
    cout << modPower(2, 10, 1000) << endl; // Output: 24
    return 0;
}

Intermediate Problems

1. Modular Inverse (a-1 % p)

Given a number a and prime p, find the modular inverse using Fermat’s Little Theorem: ap-2 % p.


#include <iostream>
using namespace std;

long long modInverse(long long a, long long p) {
    return modPower(a, p - 2, p);
}

long long modPower(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1)
            result = (result * a) % m;
        a = (a * a) % m;
        b /= 2;
    }
    return result;
}

int main() {
    cout << modInverse(3, 11) << endl; // Output: 4
    return 0;
}

2. Count Binary Strings Without Consecutive 1s

Fibonacci sequence problem that can be solved using matrix exponentiation.


#include <iostream>
using namespace std;

void multiply(long long F[2][2], long long M[2][2]) {
    long long x = F[0][0]*M[0][0] + F[0][1]*M[1][0];
    long long y = F[0][0]*M[0][1] + F[0][1]*M[1][1];
    long long z = F[1][0]*M[0][0] + F[1][1]*M[1][0];
    long long w = F[1][0]*M[0][1] + F[1][1]*M[1][1];

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

void power(long long F[2][2], int n) {
    if (n == 0 || n == 1) return;
    long long M[2][2] = {{1, 1}, {1, 0}};
    power(F, n / 2);
    multiply(F, F);
    if (n % 2 != 0)
        multiply(F, M);
}

long long fib(int n) {
    if (n == 0) return 0;
    long long F[2][2] = {{1, 1}, {1, 0}};
    power(F, n - 1);
    return F[0][0];
}

int main() {
    cout << fib(10) << endl; // Output: 55
    return 0;
}

Hard Problem

1. Large Number of Ways to Tile a 2xN Board

This can be solved using matrix exponentiation. The recurrence is: T(n) = T(n-1) + T(n-2), similar to Fibonacci.


#include <iostream>
using namespace std;

const int MOD = 1e9+7;

void multiply(long long F[2][2], long long M[2][2]) {
    long long x = (F[0][0]*M[0][0] + F[0][1]*M[1][0]) % MOD;
    long long y = (F[0][0]*M[0][1] + F[0][1]*M[1][1]) % MOD;
    long long z = (F[1][0]*M[0][0] + F[1][1]*M[1][0]) % MOD;
    long long w = (F[1][0]*M[0][1] + F[1][1]*M[1][1]) % MOD;

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

void power(long long F[2][2], int n) {
    if (n == 0 || n == 1) return;
    long long M[2][2] = {{1, 1}, {1, 0}};
    power(F, n / 2);
    multiply(F, F);
    if (n % 2 != 0)
        multiply(F, M);
}

long long countTilings(int n) {
    if (n == 0) return 0;
    long long F[2][2] = {{1, 1}, {1, 0}};
    power(F, n);
    return F[0][1];
}

int main() {
    cout << countTilings(1000000) << endl; // Fast even for large N
    return 0;
}