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
log2(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
X16is split into two partsX8andX8 - Green – the second level, where each
X8is divided intoX4 × X4 - Red – the third level, where
X4is divided intoX2 × X2, and then into the base elementsX
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 log2(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))
m:
(a × b) mod m = ((a mod m) × (b mod m)) mod m
#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 Xn, but only its remainder when divided by some number m — that is, the expression (Xn) 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 (Me mod n) is used for message encryption.
- Competitive programming: many problems require computing Xn modulo 109+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 1018).
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
mtimes is equivalent to raising the permutation to them-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
mdetermines whether the current permutation is combined with the result. - Finally, we obtain the resulting permutation of the array after applying the shuffle
mtimes. - Efficiency:
O(n log m), which allows handling very large values ofmandn.
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.
|
Previous
|< The Maximum sum of subarray |