Python中的时序模幂运算：语法与函数

Question

在Python中，如果内建的pow()函数与3个参数一起使用，则最后一个用作取幂的模数，从而产生Modular exponentiation操作。

换句话说，pow(x, y, z)等效于(x ** y) % z，但相应地，对于Python帮助，pow()可能更有效。

当我超时了两个版本，我得到了相反的结果，该pow()版本似乎比同等的语法慢：

的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 
>>> 

以上数字的解释是什么？

---

编辑：

我看到，在st_expmod版本，计算没有被运行时执行的答案后，而是由解析器和表达成为一个常数..

使用Python2中的@ user2357112建议的修复：

>>> 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

你实际上并没有计算com用**和%来表示，因为结果会被字节码编译器不断折叠。避免：

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

和pow版本将胜手。

Answer 2

一些粉饰上@ user2357112是正确答案：

首先，如果你手工调用你的两个字符串eval()，很明显，st_expmod是极其慢。

其次，它有时（就像在这种情况下）支付看生成的代码。像这样：

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

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

你并不真的需要知道很多关于Python的字节码地看到，编译后的代码只是用来加载答案（10686982），并返回它 - 当代码被所有的实际工作已完成编译。