Fast Exponentiation (Binary Exponentiation) Code Implementations
Complete Fast Exponentiation (Binary Exponentiation) code implementations in C++, Python, Java, and JavaScript with time and space complexity analysis on AntInLoop.
Read Fast Exponentiation (Binary Exponentiation) Guide ยท Launch Interactive Visualizer
C++ Implementation
// Fast Exponentiation in C++
class FastExponentiation {
public:
// Iterative
static long long fastPowIterative(long long base, long long exponent) {
long long result = 1;
while (exponent > 0) {
if (exponent % 2 == 1) {
result *= base;
}
base *= base;
exponent /= 2;
}
return result;
}
// Recursive
static long long fastPowRecursive(long long base, long long exponent) {
if (exponent == 0) return 1;
if (exponent % 2 == 0) {
long long half = fastPowRecursive(base, exponent / 2);
return half * half;
} else {
return base * fastPowRecursive(base, exponent - 1);
}
}
};JAVA Implementation
// Fast Exponentiation in Java
public class FastExponentiation {
// Iterative
public static long fastPowIterative(long base, long exponent) {
long result = 1;
while (exponent > 0) {
if ((exponent & 1) == 1) {
result *= base;
}
base *= base;
exponent >>= 1;
}
return result;
}
// Recursive
public static long fastPowRecursive(long base, long exponent) {
if (exponent == 0) return 1;
if (exponent % 2 == 0) {
long half = fastPowRecursive(base, exponent / 2);
return half * half;
} else {
return base * fastPowRecursive(base, exponent - 1);
}
}
}JAVASCRIPT Implementation
// Fast Exponentiation (Exponentiation by Squaring) in JavaScript
// Iterative
function fastPowIterative(base, exponent) {
let result = 1;
while (exponent > 0) {
if (exponent % 2 === 1) result *= base;
base *= base;
exponent = Math.floor(exponent / 2);
}
return result;
}
// Recursive
function fastPowRecursive(base, exponent) {
if (exponent === 0) return 1;
if (exponent % 2 === 0) {
const half = fastPowRecursive(base, exponent / 2);
return half * half;
} else {
return base * fastPowRecursive(base, exponent - 1);
}
}PYTHON Implementation
# Fast Exponentiation (Exponentiation by Squaring) in Python
# Iterative
def fast_pow_iterative(base, exponent):
result = 1
while exponent > 0:
if exponent % 2 == 1:
result *= base
base *= base
exponent //= 2
return result
# Recursive
def fast_pow_recursive(base, exponent):
if exponent == 0:
return 1
elif exponent % 2 == 0:
half = fast_pow_recursive(base, exponent // 2)
return half * half
else:
return base * fast_pow_recursive(base, exponent - 1)