python pow函數(shù)的底層實(shí)現(xiàn)原理介紹

更新時(shí)間：2021年03月12日 09:38:01 作者：喲，寫bug呢？？

這篇文章主要介紹了python pow函數(shù)的底層實(shí)現(xiàn)原理介紹，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧

一、最樸素的方法和pow比較

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

最容易想到的方法就是：循環(huán)b次，每次都乘以a。但是究竟底層是不是這樣實(shí)現(xiàn)的呢？

下面先從時(shí)間上來判斷他們之間的關(guān)系。

首先來看看，pow和**有沒有區(qū)別：

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

上面的結(jié)果輸出如下：

2的100萬次方，兩者所用時(shí)間是基本一樣的，所以他們應(yīng)該本質(zhì)上應(yīng)該使用了相同的算法

下面再來看看用for循環(huán)模擬的結(jié)果

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

上面的輸入結(jié)果如下:

非常恐怖的對(duì)比，pow和**都只用了1.5秒，而for循環(huán)用來20秒！，所以可以肯定的是，pow底層絕對(duì)不是用循環(huán)去求解的

二、pow底層實(shí)現(xiàn)

我們分析一下為什么直接循環(huán)相乘效率會(huì)這么低，我們其實(shí)不難發(fā)現(xiàn)里面有大量的重復(fù)運(yùn)算，比如我們算出22后面，還不斷重復(fù)著計(jì)算22的結(jié)果，所以我們只要保存這些中間必要的計(jì)算結(jié)果后你不斷重復(fù)利用就可以大大減少運(yùn)算量。

舉個(gè)例子，比如我們現(xiàn)在在計(jì)算2的9次方，我們可以這樣子計(jì)算，先算出22然后不斷利用這個(gè)結(jié)果：（22）（22）（22）（22）2 即44442 只要計(jì)算5次

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

具體實(shí)現(xiàn)程序如下：

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

接下我們來看看，究竟pow函數(shù)底層是不是這樣實(shí)現(xiàn)的

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