python pow函數的底層實現原理介紹

python中求兩個a的b次方，常見的方法有:pow(a,b),a**b。那么這兩個是否有區別，而且他們底層是怎么實現的呢？

最容易想到的方法就是：循環b次，每次都乘以a。但是究竟底層是不是這樣實現的呢？

下面先從時間上來判斷他們之間的關系。

首先來看看，pow和**有沒有區別：

import timestart = time.time()print(2 ** 1000000)end0 = time.time()print(’**:’, end0 - start)print(pow(2, 1000000))end1 = time.time()print(’pow:’, end1 - end0)

上面的結果輸出如下：

2的100萬次方，兩者所用時間是基本一樣的，所以他們應該本質上應該使用了相同的算法

下面再來看看用for循環模擬的結果

import timestart = time.time()print(2 ** 1000000)end0 = time.time()print(’**:’, end0 - start)print(pow(2, 1000000))end1 = time.time()print(’pow:’, end1 - end0)r = 1for i in range(1000000): r *= 2end2 = time.time()print(’for:’, end2 - end1)

上面的輸入結果如下:

非?？植赖膶Ρ?，pow和**都只用了1.5秒，而for循環用來20秒！，所以可以肯定的是，pow底層絕對不是用循環去求解的

我們分析一下為什么直接循環相乘效率會這么低，我們其實不難發現里面有大量的重復運算，比如我們算出22后面，還不斷重復著計算22的結果，所以我們只要保存這些中間必要的計算結果后你不斷重復利用就可以大大減少運算量。

舉個例子，比如我們現在在計算2的9次方，我們可以這樣子計算，先算出22然后不斷利用這個結果：（22）（22）（22）（22）2 即44442 只要計算5次

同理可以再利用上面的44 可以的16162

具體實現程序如下：

def fun(a, b): r = 1 while b > 1: if b & 1 == 1: #與運算一般可以用于取某位數，這里就是取最后一位。 r *= a a *= a b = b >> 1 #這里等價于b//=2 return r * a

接下我們來看看，究竟pow函數底層是不是這樣實現的

import timestart = time.time()print(2 ** 1000000)end0 = time.time()print(’**:’, end0 - start)print(pow(2, 1000000))end1 = time.time()print(’pow:’, end1 - end0)r = 1for i in range(1000000): r *= 2end2 = time.time()print(’for:’, end2 - end1)print(fun(2, 1000000))print(’fun:’, time.time() - end2)

從上面可以看出來，pow函數運行的時間基本和自定義的函數一致，甚至自定制的還更快！

解析完畢！

補充：Python3 的pow函數用法 及效率

1. pow（a,b） 表示求a的b次方 a^b

2.pow(a,b,c) 表示求a的b次方取余c a^b%c

然后 用pow函數求出來的 a^b%c 時間上可以與“快速冪取模算法” 相媲美！

以上為個人經驗，希望能給大家一個參考，也希望大家多多支持好吧啦網。如有錯誤或未考慮完全的地方，望不吝賜教。