Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Calculating powers (e.g. 2^11) quickly [duplicate]

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?

like image 563
Meir Avatar asked Feb 04 '10 08:02

Meir


People also ask

How do you calculate power of 2 quickly?

When multiplying 2x × 2y, remember that you simply add the exponents together. For example, 23 (8) × 27 (128) = 27+3 = 210 (1024). Similarly, you can break up a single power of 2 into two powers which add up to the original power, such as 29 (512) = 26+3 = 26 (64) × 23 (8).

What is the easiest way to find 2 10?

Answer: The value of 2 raised to 10th power i.e., 210 is 1024. Let us calculate the value of 2 raised to 10th power i.e., 210. Thus, 210 can be written as 25 × 25.


4 Answers

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
like image 85
Omnifarious Avatar answered Nov 04 '22 12:11

Omnifarious


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

like image 29
jhchen Avatar answered Nov 04 '22 13:11

jhchen


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.

like image 39
Karl Avatar answered Nov 04 '22 12:11

Karl


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

like image 43
SebastianK Avatar answered Nov 04 '22 12:11

SebastianK