Speed of Calculating Powers (In Python)

Speed of calculating powers (in python)

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.

What is the fastest way to calculate / create powers of ten?

You're comparing apples to oranges here. 10 ** n computes an integer (when n is non-negative), whereas float(f'1e{n}') computes a floating-point number. Those won't take the same amount of time, but they solve different problems so it doesn't matter which one is faster.

But it's worse than that, because there is the overhead of calling a function, which is included in your timing for all of your alternatives, but only some of them actually involve calling a function. If you write 10 ** n then you aren't calling a function, but if you use partial(pow, 10) then you have to call it as a function to get a result. So you're not actually comparing the speed of 10 ** n fairly.

Instead of rolling your own timing code, use the timeit library, which is designed for doing this properly. The results are in seconds for 1,000,000 repetitions (by default), or equivalently they are the average time in microseconds for one repetiton.

Here's a comparison for computing integer powers of 10:

>>> from timeit import timeit
>>> timeit('10 ** n', setup='n = 500')
1.09881673199925
>>> timeit('pow(10, n)', setup='n = 500')
1.1821871869997267
>>> timeit('f(n)', setup='n = 500; from functools import partial; f = partial(pow, 10)')
1.1401332350014854

And here's a comparison for computing floating-point powers of 10: note that computing 10.0 ** 500 or 1e500 is pointless because the result is simply an OverflowError or inf.

>>> timeit('10.0 ** n', setup='n = 200')
0.12391662099980749
>>> timeit('pow(10.0, n)', setup='n = 200')
0.17336435099969094
>>> timeit('f(n)', setup='n = 200; from functools import partial; f = partial(pow, 10.0)')
0.18887039500077663
>>> timeit('float(f"1e{n}")', setup='n = 200')
0.44305286100097874
>>> timeit('np.power(10.0, n, dtype=float)', setup='n = 200; import numpy as np')
1.491982370000187
>>> timeit('f(n)', setup='n = 200; from functools import partial; import numpy as np; f = partial(np.power, 10.0, dtype=float)')
1.6273324920002779

So the fastest of these options in both cases is the obvious one: 10 ** n for integers and 10.0 ** n for floats.

Why is pow(a, d, n) so much faster than a**d % n?

See the Wikipedia article on modular exponentiation. Basically, when you do a**d % n, you actually have to calculate a**d, which could be quite large. But there are ways of computing a**d % n without having to compute a**d itself, and that is what pow does. The ** operator can't do this because it can't "see into the future" to know that you are going to immediately take the modulus.

What's the most efficient algorithm to compute powers?

Calculate the binary powers of base modulo n by squaring the previous binary power e.g. base^2=base^1*base^1; base^4 = base^2*base^2

By binary I mean base^0, base^1, base^2, base^4, base^8 etc.

Then multiple the binary powers when the bit is set in the exponent.

E.g. exponent 9: base^9 = base^1 * base^8.
All calculations are done in modulo n.

Find attached the pseudocode; I hope it is correct because it is untested;

//pseudocode
function myPower(base, exponent, n) {
    power = 1;
    binarypower = base;
    while(exponent>0) {
        if(exponent&1 != 0) {
            power = (binarypower * power) %n;
        }
        exponent = exponent>>1;
        if(exponent>0) {
            binarypower = (binarypower*binarypower)%n;
        }
    }
    return power;
}

* vs ** for a power of 2 operation

I do not agree with g.d.d.c, multiplication is much faster !

"""Evaluating the difference in execution time between n*n and n**2"""

from time import time

n = 2
t = time()
for i in range(5000000):
    n**2
print("Time for n**2:\t%0.3f" % (time()-t))
t = time()
for i in range(5000000):
    n*n
print("Time for n*n:\t%0.3f" % (time()-t))

def test(n):
    """
    Difference in execution time between n*n and n**2
    within function scope.
    """
    t = time()
    for i in range(5000000):
        n**2
    print("Time for n**2:\t%0.3f" % (time()-t))
    t = time()
    for i in range(5000000):
        n*n
    print("Time for n*n:\t%0.3f" % (time()-t))

test(n)

Results :

Time for n**2: 2.324496030807495
Time for n*n:  0.5879969596862793
Time for n**2: 2.0771241188049316
Time for n*n:  0.2894318103790283

You can see that multiplication is about 4 times faster outside of a function, and 7 times faster in the function. I cannot explain the difference between those two tests, and I am not sure about the difference between n*n and n**2, but it might be related with the fact that Python is an interpreted language, and the processing of the latter takes more time, even if the processor operations are very similar, as g.d.d.c demonstrates.

Why is x**3 slower than x*x*x?

As per this answer, it's because the implementation of exponentiation has some overhead that multiplication does not. However, naive multiplication will get slower and slower as the exponent increases. An empirical demonstration:

 In [3]: x = np.random.rand(1e6)

 In [15]: %timeit x**2
 100 loops, best of 3: 11.9 ms per loop

 In [16]: %timeit x*x
 100 loops, best of 3: 12.7 ms per loop

 In [17]: %timeit x**3
 10 loops, best of 3: 132 ms per loop

 In [18]: %timeit x*x*x
 10 loops, best of 3: 27.2 ms per loop

 In [19]: %timeit x**4
 10 loops, best of 3: 132 ms per loop

 In [20]: %timeit x*x*x*x
 10 loops, best of 3: 42.4 ms per loop

 In [21]: %timeit x**10
 10 loops, best of 3: 132 ms per loop

 In [22]: %timeit x*x*x*x*x*x*x*x*x*x
 10 loops, best of 3: 137 ms per loop

 In [24]: %timeit x**15
 10 loops, best of 3: 132 ms per loop

 In [25]: %timeit x*x*x*x*x*x*x*x*x*x*x*x*x*x*x
 1 loops, best of 3: 212 ms per loop

Note the exponentiation time stays more or less constant, except for the x**2 case which I suspect is special-cased, while multiplication gets slower and slower. It seems you could exploit this to get faster integer exponentiation... for example:

In [26]: %timeit x**16
10 loops, best of 3: 132 ms per loop

In [27]: %timeit x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x
1 loops, best of 3: 225 ms per loop

In [28]: def tosixteenth(x):
   ....:     x2 = x*x
   ....:     x4 = x2*x2
   ....:     x8 = x4*x4
   ....:     x16 = x8*x8
   ....:     return x16
   ....:

In [29]: %timeit tosixteenth(x)
10 loops, best of 3: 49.5 ms per loop

It seems you could apply this technique generically by splitting any integer into a sum of the powers of two, computing each power of two as above, and summing:

In [93]: %paste
def smartintexp(x, exp):
    result = np.ones(len(x))
    curexp = np.array(x)
    while True:
        if exp%2 == 1:
            result *= curexp
        exp >>= 1
        if not exp: break
        curexp *= curexp
    return result
## -- End pasted text --

In [94]: x
Out[94]:
array([ 0.0163407 ,  0.57694587,  0.47336487, ...,  0.70255032,
        0.62043303,  0.0796748 ])

In [99]: x**21
Out[99]:
array([  3.01080670e-38,   9.63466181e-06,   1.51048544e-07, ...,
         6.02873388e-04,   4.43193256e-05,   8.46721060e-24])

In [100]: smartintexp(x, 21)
Out[100]:
array([  3.01080670e-38,   9.63466181e-06,   1.51048544e-07, ...,
         6.02873388e-04,   4.43193256e-05,   8.46721060e-24])

In [101]: %timeit x**21
10 loops, best of 3: 132 ms per loop

In [102]: %timeit smartintexp(x, 21)
10 loops, best of 3: 70.7 ms per loop

It's fast for small even powers of two:

In [106]: %timeit x**32
10 loops, best of 3: 131 ms per loop

In [107]: %timeit smartintexp(x, 32)
10 loops, best of 3: 57.4 ms per loop

But gets slower as the exponent gets larger:

In [97]: %timeit x**63
10 loops, best of 3: 133 ms per loop

In [98]: %timeit smartintexp(x, 63)
10 loops, best of 3: 110 ms per loop

And not faster for large worst-cases:

In [115]: %timeit x**511
10 loops, best of 3: 135 ms per loop

In [114]: %timeit smartintexp(x, 511)
10 loops, best of 3: 192 ms per loop

---

Related Topics