Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Speed of calculating powers (in python)

I'm curious as to why it's so much faster to multiply than to take powers in python (though from what I've read this may well be true in many other languages too). For example it's much faster to do

x*x 

than

x**2 

I suppose the ** operator is more general and can also deal with fractional powers. But if that's why it's so much slower, why doesn't it perform a check for an int exponent and then just do the multiplication?

Edit: Here's some example code I tried...

def pow1(r, n):   for i in range(r):     p = i**n  def pow2(r, n):   for i in range(r):     p = 1     for j in range(n):       p *= i 

Now, pow2 is just a quick example and is clearly not optimised!
But even so I find that using n = 2 and r = 1,000,000, then pow1 takes ~ 2500ms and pow2 takes ~ 1700ms.
I admit that for large values of n, then pow1 does get much quicker than pow2. But that's not too surprising.

like image 925
Christwo Avatar asked Jun 19 '09 19:06

Christwo


People also ask

Is POW faster than multiplication Python?

pow() is more efficient than chained multiplication at powers larger than 5 and always more efficient than the ** operator, so there is never a reason to use ** .


1 Answers

Basically naive multiplication is O(n) with a very low constant factor. Taking the power is O(log n) with a higher constant factor (There are special cases that need to be tested... fractional exponents, negative exponents, etc) . Edit: just to be clear, that's O(n) where n is the exponent.

Of course the naive approach will be faster for small n, you're only really implementing a small subset of exponential math so your constant factor is negligible.

like image 88
patros Avatar answered Sep 24 '22 23:09

patros