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](https://en.wikipedia.org/wiki/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.

