Fast Exponentiation Algorithm — Explanation and Examples

Fast exponentiation (exponentiation by squaring) is an efficient algorithm for computing the value of Xn — that is, raising a number X to the power of n. This approach significantly speeds up calculations compared to simple repeated multiplication.

Step 1 — The Naive Approach

The naive method starts by setting the result to 1 and then multiplies it by X exactly n times in a loop. Although straightforward, this method has a time complexity of O(n) and becomes too slow for large exponents.

#include <iostream>
using namespace std;

// Naive approach to exponentiation
long long naiveExponentiation(long long base, long long exponent) {
    long long result = 1;

    // Multiply 'result' by 'base' exactly 'exponent' times
    for (long long i = 0; i < exponent; ++i) {
        result *= base;
    }

    return result;
}

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

Step 2 — The Core Idea of the Algorithm

The key observation behind fast exponentiation is that the exponent can be halved whenever it is even:
Xn = Xn/2 × Xn/2

Instead of performing n consecutive multiplications, the exponent is halved at each recursive step. In this way, the total number of operations is reduced from n to approximately log₂(n) multiplications — resulting in a major performance improvement.

Figure 1 shows an example of fast exponentiation for n = 16. The problem is solved by recursively halving the exponent at each level:
X16 = X8 × X8, then X8 = X4 × X4, and so on until we reach the base case X1.

The illustration clearly marks the recursion levels:

• Blue – the first recursion level, where X16 is split into two parts X8 and X8
• Green – the second level, where each X8 is divided into X4 × X4
• Red – the third level, where X4 is divided into X2 × X2, and then into the base elements X

This visual breakdown helps illustrate how the algorithm minimizes the number of operations: each halving of the exponent corresponds to one recursion level, making the total number of levels equal to log₂(n).

#include <iostream>
using namespace std;

// Recursive implementation of fast exponentiation
long long fastExponentiation(long long base, long long exp) {
    // Base case: any number to the power of 0 equals 1
    if (exp == 0)
        return 1;

    // Recursively compute half of the exponent
    long long half = fastExponentiation(base, exp / 2);

    // If the exponent is even: Xⁿ = (X^(n/2))²
    if (exp % 2 == 0)
        return half * half;
    else
        // If the exponent is odd: Xⁿ = X × (X^(n/2))²
        return base * half * half;
}

int main() {
    cout << fastExponentiation(2, 16) << endl; // Output: 65536
    return 0;
}
    

Step 3 — Handling Odd Exponents

When the exponent is odd, it can be expressed as n = 2k + 1. In that case:
X2k+1 = X × X2k

So, for an odd exponent, we first calculate X2k (as if the exponent were even), and then multiply the result by one additional X. This keeps the algorithm simple and efficient, with just one extra multiplication.

#include <iostream>
using namespace std;

// Fast exponentiation with explicit handling for even and odd cases
long long fastExponentiationDetailed(long long base, long long exp) {
    if (exp == 0)
        return 1;

    if (exp % 2 == 0) {
        // Even exponent: n = 2k
        long long half = fastExponentiationDetailed(base, exp / 2);
        return half * half;
    } else {
        // Odd exponent: n = 2k + 1
        long long half = fastExponentiationDetailed(base, (exp - 1) / 2);
        long long square = half * half;
        return base * square;
    }
}

int main() {
    cout << fastExponentiationDetailed(3, 13) << endl; // Output: 1594323
    return 0;
}
    

This approach can be easily extended to modular exponentiation, where results are reduced modulo a given number (e.g. mod 1000000007), a common technique in programming and cryptography.

Step 4 — Fast Exponentiation for Odd Exponents

So far, we’ve seen that for an even exponent n, the following holds:
Xn = Xn/2 × Xn/2.

However, when the exponent is odd, it can be expressed as:
n = 2k + 1, where k is an integer.

In that case, we have the relation:
Xn = X × X2k, or equivalently:
X2k+1 = X × (Xk)².

This means that the fast exponentiation algorithm must include an additional multiplication by X when the exponent is odd. This approach keeps the algorithm efficient, since the number of recursive calls still decreases approximately logarithmically with respect to the size of the exponent.

#include <iostream>
using namespace std;

// Function implementing fast exponentiation for all cases
long long fastExponentiationOdd(long long base, long long exp) {
    // Base case — any number to the power of 0 is 1
    if (exp == 0)
        return 1;

    // Recursively compute half of the exponent
    long long half = fastExponentiationOdd(base, exp / 2);

    // If the exponent is even: n = 2k
    if (exp % 2 == 0)
        return half * half;
    else {
        // If the exponent is odd: n = 2k + 1
        // Result: X × (X^(k))²
        return base * half * half;
    }
}

int main() {
    cout << "2^7 = " << fastExponentiationOdd(2, 7) << endl;   // Outputs: 128
    cout << "3^5 = " << fastExponentiationOdd(3, 5) << endl;   // Outputs: 243
    cout << "5^3 = " << fastExponentiationOdd(5, 3) << endl;   // Outputs: 125
    return 0;
}
    

As shown in the example, the algorithm correctly handles odd exponents. For each odd exponent, one extra multiplication by the base X is performed, while for even exponents, the result is obtained by squaring half the exponent.

The overall time complexity remains O(log n), making this approach significantly faster than the naive method.

// Example for 3^13
// n = 13 → 13 = 2*6 + 1 → X^(13) = X * (X^6)^2

// First compute X^6:
// X^6 = (X^3)^2 = ((X^1)^2 * X)^2
// then X^13 = X * (X^6)^2

// Therefore, 3^13 = 3 * (3^6)^2 = 3 * (729)^2 = 3 * 531441 = 1594323
    

This makes it easy to follow the recursive flow of the algorithm: each recursive branch halves the exponent until it reaches zero, where the base case returns 1.

Step 5 — Modular Fast Exponentiation

In many problems, especially in algorithms and competitive programming, it is often necessary to compute large powers of numbers while keeping the result within a specific modulus (m), usually to prevent numeric overflow.

Such expressions are typically written as:
(Xn) mod m

Modular fast exponentiation is based on the same principle as the regular version:

• If the exponent is even, Xn = (Xn/2)²
• If the exponent is odd, Xn = X × (X(n−1))

#include <iostream>
using namespace std;

// Function that efficiently computes (base^exp) % mod
long long modularExponentiation(long long base, long long exp, long long mod) {
    // Base case: any number to the power of 0 is 1
    if (exp == 0)
        return 1;

    // Recursively compute half the exponent
    long long half = modularExponentiation(base, exp / 2, mod);

    // Compute the squared result modulo m
    long long result = (half * half) % mod;

    // If the exponent is odd, multiply once more by base mod m
    if (exp % 2 == 1)
        result = (result * (base % mod)) % mod;

    return result;
}

int main() {
    long long base = 7, exp = 13, mod = 1000;
    cout << "(" << base << "^" << exp << ") % " << mod << " = "
         << modularExponentiation(base, exp, mod) << endl;

    // Additional tests
    cout << "(3^20) % 50 = " << modularExponentiation(3, 20, 50) << endl;
    cout << "(2^30) % 17 = " << modularExponentiation(2, 30, 17) << endl;

    return 0;
}
    

In each step, the % mod operation ensures that intermediate results remain within the given bounds. This prevents overflow, which is especially important when both X and n are very large.

For example, the expression:
(713) mod 1000 yields:
343, and is computed efficiently using only a few recursive calls.

Complexity analysis:
The algorithm runs in O(log n) time since the exponent is halved in each step. This makes it many times faster than the naive approach, which has O(n) complexity.

// (7^13) % 1000
// n = 13 → odd → 7 * (7^6)^2 % 1000
// (7^6) = ((7^3)^2) % 1000
// (7^3) = 7 * (7^1)^2 % 1000
// Each intermediate result is computed modulo 1000

// Final result: 343
    

Modular fast exponentiation is a fundamental tool in many algorithms — it is widely used in cryptography, hash functions, number theory, and most competitive programming problems involving large numbers.

Modular Version of the Algorithm

In many programming and cryptography problems, it’s not necessary to compute the full result of Xⁿ, but only its remainder when divided by some number m — that is, the expression (Xⁿ) mod m. This technique is called modular exponentiation and is crucial in areas such as:

• cryptography (e.g., RSA algorithm, Diffie–Hellman key exchange),
• competitive programming (computing large powers with limited results),
• big-number arithmetic optimization.

The main idea is to take the remainder modulo m in each step of the algorithm, keeping intermediate values small and avoiding overflow. The basic properties of modular arithmetic allow the following:

(X × Y) mod m = ((X mod m) × (Y mod m)) mod m

Based on this rule, we can easily adapt the iterative version of the fast exponentiation algorithm:

// Modular version of fast exponentiation (X^n mod m)
#include <iostream>
using namespace std;

long long fastExponentiationModular(long long base, long long exp, long long mod)
{
    long long result = 1;
    base = base % mod; // ensure the base is within the modulus range

    while (exp > 0)
    {
        // If the current bit of the exponent is 1, include the base in the result
        if (exp % 2 == 1)
            result = (result * base) % mod;

        // Square the base and take mod
        base = (base * base) % mod;

        // Divide exponent by 2
        exp /= 2;
    }

    return result;
}

int main()
{
    long long x, n, m;

    cout << "Enter base: ";
    cin >> x;

    cout << "Enter exponent: ";
    cin >> n;

    cout << "Enter modulus: ";
    cin >> m;

    cout << "( " << x << "^" << n << " ) mod " << m << " = " 
         << fastExponentiationModular(x, n, m) << endl;

    return 0;
}

Algorithm Explanation

• Step 1: Each multiplication is taken modulo m to prevent overflow.
• Step 2: When the exponent is odd, the current base is included in the result (also modulo m).
• Step 3: The base is squared and reduced by modulo again, ensuring efficiency and safety.
• Step 4: The exponent is divided by 2 in each loop iteration (binary decomposition).

Practical Applications

Modular exponentiation is used wherever large powers of numbers are required but results must remain bounded:

• Cryptography: in the RSA algorithm, the expression (M^e mod n) is used for message encryption.
• Competitive programming: many problems require computing Xⁿ modulo 10⁹+7.
• Simulations and games: when repeated power calculations must stay within controlled limits.

Complexity Analysis

The algorithm runs in O(log n) time, since the exponent is divided by 2 at each step. This means the number of operations is proportional to the number of bits in the binary representation of the exponent.

13. SHUFFLER — Applying the Fast Exponentiation Algorithm

See the original problem statement here

View the complete solution and explanation

The task “Shuffler” requires applying a given shuffling pattern to an array 0, 1, 2, ..., n-1 exactly m times. If we were to apply the shuffle naively, one by one, m times, the execution time would be far too long for large m (up to 10¹⁸). This is where the fast exponentiation of permutations algorithm becomes extremely useful.

Algorithm Description

• Each shuffle operation can be viewed as a permutation of the array.
• Applying the shuffle m times is equivalent to raising the permutation to the m-th power.
• By combining permutations through binary exponentiation, we obtain the final position of each element efficiently.
• This approach has a time complexity of O(n log m), which is optimal for the given constraints.

Example Solution in C++

#include <iostream>
#include <vector>

using namespace std;

// Function that combines two permutations
vector<int> combinePermutations(const vector<int>& a, const vector<int>& b) {
    int n = a.size();
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        c[i] = a[b[i]]; // The element from position b[i] moves to position i
    }
    return c;
}

// Fast exponentiation of permutation
vector<int> fastPowerPermutation(vector<int> perm, long long m) {
    int n = perm.size();
    vector<int> result(n);
    for (int i = 0; i < n; i++) result[i] = i; // Identity permutation

    while (m > 0) {
        if (m % 2 == 1) {
            result = combinePermutations(result, perm); // Combine when the bit is set
        }
        perm = combinePermutations(perm, perm); // Square the permutation
        m /= 2;
    }

    return result;
}

int main() {
    int n;
    long long m;
    cin >> n >> m;

    vector<int> shuffle(n);
    for (int i = 0; i < n; i++) cin >> shuffle[i];

    vector<int> finalPosition = fastPowerPermutation(shuffle, m);

    for (int i = 0; i < n; i++) {
        if (i > 0) cout << " ";
        cout << finalPosition[i];
    }
    cout << endl;

    return 0;
}

Code Explanation

• combinePermutations: merges two permutations so that the result is equivalent to applying both in sequence.
• fastPowerPermutation: uses binary exponentiation for permutations; each bit of the exponent m determines whether the current permutation is combined with the result.
• Finally, we obtain the resulting permutation of the array after applying the shuffle m times.
• Efficiency:O(n log m), which allows handling very large values of m and n.

Conclusion

This example demonstrates how the fast exponentiation algorithm can be applied beyond numerical problems — specifically, to permutations. Such usage is common in competitive programming, simulations, and problems involving cyclic transformations of arrays.