Calculating powers (e.g. 2^11) quickly
algorithm, exponent
Solution
There is a generalized algorithm for this, but in languages that have bit-shifting, there's a much faster way to compute powers of 2. You just put in `1 << exp` (assuming your bit shift operator is `<<` as it is in most languages that support the operation).
I assume you're looking for the generalized algorithm and just chose an unfortunate base as an example. I will give this algorithm in Python.
def intpow(base, exp):
if exp == 0:
return 1
elif exp == 1:
return base
elif (exp & 1) != 0:
return base * intpow(base * base, exp // 2)
else:
return intpow(base * base, exp // 2)
This basically causes exponents to be able to be calculated in log2 exp time. It's a divide and conquer algorithm. :-) As someone else said exponentiation by squaring.
If you plug your example into this, you can see how it works and is related to the equation you give:
intpow(2, 13)
2 * intpow(4, 6)
2 * intpow(16, 3)
2 * 16 * intpow(256, 1)
2 * 16 * 256 == 2^1 * 2^4 * 2^8
Problem
Possible Duplicate: The most efficient way to implement an integer based power function pow(int, int) How can I calculate powers with better runtime? E.g. 2^13. I remember seeing somewhere that it has something to do with the following calculation: 2^13 = 2^8 * 2^4 * 2^1 But I can't see how calculating each component of the right side of the equation and then multiplying them would help me. Any ideas? Edit: I did mean with any base. How do the algorithms you've mentioned below, in particular the "Exponentation by squaring", improve the runtime / complexity?