Fabiano Fabiano - 6 months ago 28
Python Question

Timing Modular Exponentiation in Python: syntax vs function

In Python, if the builtin

pow()
function is used with 3 arguments, the last one is used as the modulus of the exponentiation, resulting in a Modular exponentiation operation.

In other words,
pow(x, y, z)
is equivalent to
(x ** y) % z
, but accordingly to Python help, the
pow()
may be more efficient.

When I timed the two versions, I got the opposite result, the
pow()
version seemed slower than the equivalent syntax:

Python 2.7:

>>> import sys
>>> print sys.version
2.7.11 (default, May 2 2016, 12:45:05)
[GCC 4.9.3]
>>>
>>> help(pow)

Help on built-in function pow in module __builtin__: <F2> Show Source

pow(...)
pow(x, y[, z]) -> number

With two arguments, equivalent to x**y. With three arguments,
equivalent to (x**y) % z, but may be more efficient (e.g. for longs).

>>>
>>> import timeit
>>> st_expmod = '( 65537 ** 767587 ) % 14971787'
>>> st_pow = 'pow(65537, 767587, 14971787)'
>>>
>>> timeit.timeit(st_expmod)
0.016651153564453125
>>> timeit.timeit(st_expmod)
0.016621112823486328
>>> timeit.timeit(st_expmod)
0.016611099243164062
>>>
>>> timeit.timeit(st_pow)
0.8393168449401855
>>> timeit.timeit(st_pow)
0.8449611663818359
>>> timeit.timeit(st_pow)
0.8767969608306885
>>>


Python 3.4:

>>> import sys
>>> print(sys.version)
3.4.3 (default, May 2 2016, 12:47:35)
[GCC 4.9.3]
>>>
>>> help(pow)

Help on built-in function pow in module builtins:

pow(...)
pow(x, y[, z]) -> number

With two arguments, equivalent to x**y. With three arguments,
equivalent to (x**y) % z, but may be more efficient (e.g. for ints).

>>>
>>> import timeit
>>> st_expmod = '( 65537 ** 767587 ) % 14971787'
>>> st_pow = 'pow(65537, 767587, 14971787)'
>>>
>>> timeit.timeit(st_expmod)
0.014722830994287506
>>> timeit.timeit(st_expmod)
0.01443593599833548
>>> timeit.timeit(st_expmod)
0.01485627400688827
>>>
>>> timeit.timeit(st_pow)
3.3412855619972106
>>> timeit.timeit(st_pow)
3.2800855879904702
>>> timeit.timeit(st_pow)
3.323372773011215
>>>


Python 3.5:

>>> import sys
>>> print(sys.version)
3.5.1 (default, May 2 2016, 14:34:13)
[GCC 4.9.3
>>>
>>> help(pow)

Help on built-in function pow in module builtins:

pow(x, y, z=None, /)
Equivalent to x**y (with two arguments) or x**y % z (with three arguments)

Some types, such as ints, are able to use a more efficient algorithm when
invoked using the three argument form.

>>>
>>> import timeit
>>> st_expmod = '( 65537 ** 767587 ) % 14971787'
>>> st_pow = 'pow(65537, 767587, 14971787)'
>>>
>>> timeit.timeit(st_expmod)
0.014827249979134649
>>> timeit.timeit(st_expmod)
0.014763347018742934
>>> timeit.timeit(st_expmod)
0.014756042015505955
>>>
>>> timeit.timeit(st_pow)
3.6817933860002086
>>> timeit.timeit(st_pow)
3.6238356370013207
>>> timeit.timeit(st_pow)
3.7061628740048036
>>>


What is the explanation for the above numbers?




Edit:

After the answers I see that in the
st_expmod
version, the computation were not being executed in runtime, but by the parser and the expression became a constant..

Using the fix suggested by @user2357112 in Python2:

>>> timeit.timeit('(a**b) % c', setup='a=65537; b=767587; c=14971787', number=150)
370.9698350429535
>>> timeit.timeit('pow(a, b, c)', setup='a=65537; b=767587; c=14971787', number=150)
0.00013303756713867188

Answer

You're not actually timing the computation with ** and %, because the result gets constant-folded by the bytecode compiler. Avoid that:

timeit.timeit('(a**b) % c', setup='a=65537; b=767587; c=14971787')

and the pow version will win hands down.