Introduction
Binary exponentiation (also known as exponentiation by squaring) is a trick which allows to calculate using only multiplications (instead of multiplications required by the naive approach).
The following recursive approach expresses the same idea:
Implementation
Recursive
def binpow(a, b):
if b == 0: return 1
res = binpow(a, b // 2)
if b % 2 == 0:
return res * res
else:
return res * res * a
Iterative
def binpow(a, b):
res = 1
while b > 0:
if b & 1:
res *= a
a *= a
b >>= 1
return res
Complexity
- Time complexity:
- Space complexity: