Timing Modular Exponentiation in Python: syntax vs function

Question

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 1

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.

Answer 2

Some glosses on @user2357112's correct answer:

First, if you call eval() on your two strings by hand, it's obvious that st_expmod is enormously slower.

Second, it sometimes (like in this case) pays to look at the generated code. Like so:

>>> def f():
...     return ( 65537 ** 767587 ) % 14971787

>>> from dis import dis
>>> dis(f)
  2           0 LOAD_CONST               5 (10686982)
              3 RETURN_VALUE
>>>

You don't really need to know much about Python's byte code to see that the compiled code just loads the answer (10686982) and returns it - all the real work was done when the code was compiled.