views:

350

answers:

6

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?

+7  A: 

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
Omnifarious
+1  A: 

Powers of two are the easy ones. In binary 2^13 is a one followed by 13 zeros.

You'd use bit shifting, which is a built in operator in many languages.

Karl
+3  A: 

You can use exponentiation by squaring. This is also known as "square-and-multiply" and works for bases != 2, too.

SebastianK
It's really easy to link to wikipedia, and I think links to wikipedia make great supplements to answers, but a link to wikipedia is not an answer except when the answer is really too huge to write down here.
Omnifarious
Why invent the wheel twice? Often, the only crucial thing is to get the right keyword to name a problem.
SebastianK
+1  A: 

If you're not limiting yourself to powers of two, then:

k^2n = (k^n)^2

Thom Smith
+4  A: 

Use bitwise shifting. Ex. 1 << 11 returns 2^11.

jcmoney
2 was used as an example base only. Question is more generic.
Roman Boiko
+1  A: 

The fastest free algorithm I know of is by Phillip S. Pang, Ph.D and can the source code can be found here. It uses table-driven decomposition, by which it is possible to make exp() function, which is 2-10 times faster, then native exp() of Pentium(R) processor.

Suraj Chandran