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），並返回它 - 當代碼被所有的實際工作已完成編譯。