投稿作者 OIer，目前對(duì)計(jì)算機(jī)及算法的了解主要在信息學(xué)競(jìng)賽方面。

本文主要講解平方求冪（快速冪）相關(guān)，凡涉及大整數(shù)，都會(huì)進(jìn)行對(duì)定值取模等處理，所以存儲(chǔ)越界導(dǎo)致的錯(cuò)誤、位數(shù)過(guò)多導(dǎo)致的單次運(yùn)算緩慢的問(wèn)題，不在考慮范圍之內(nèi)。

“冪”在許多地方常被用到，如 Hash 相關(guān)、費(fèi)馬小定理、進(jìn)制轉(zhuǎn)換等。

一般來(lái)說(shuō)，我們要求 ，只需要將 乘 次即可，時(shí)間復(fù)雜度為 。

但有時(shí)， 極大，這種方法需要的時(shí)間開(kāi)銷(xiāo)是不可接受的。

比如，求 。

如果我們直接計(jì)算多個(gè)這樣的式子，至少在目前主流計(jì)算機(jī)中，所用時(shí)間以分鐘計(jì)。

我們考慮如何優(yōu)化對(duì) 的計(jì)算。

以計(jì)算 為例。

我們發(fā)現(xiàn)，，所以我們可以先計(jì)算出 ，再計(jì)算 。

于是我們想到一種方法：先計(jì)算 ，

再計(jì)算 。

這樣，我們就可以通過(guò)把 分解為約 個(gè)大小為 的塊，將時(shí)間復(fù)雜度由 降為 。

事實(shí)上，如果遞歸下去，這個(gè)做法可以做到 ，但常數(shù)較大，經(jīng)測(cè)試速度約為下面兩種做法的 。

我們?nèi)匀灰? 為例，考慮一下 可以表示成什么。

我們考慮 ，于是我們考慮通過(guò) 的值求出 。設(shè) ，有：

這樣我們就可以寫(xiě)出一份遞歸的偽代碼：

function?power(a,?n):
?if?n?=?0?then?return?1
?t?:=?power(a,?(n?-?n?mod?2)?/?2)
?if?n?mod?2?=?1
?then:?return?t^2?*?a
?else:?return?t^2
每次將數(shù)據(jù)規(guī)?？s小為原來(lái)的一半，這種方法的時(shí)空復(fù)雜度是 。

接下來(lái)仍然以計(jì)算 為例，假設(shè)你什么也不知道，只會(huì)由小向大計(jì)算，那么：

第一次乘法，只能計(jì)算 。

第二次，考慮得到盡量大的值，于是計(jì)算得 。

第三次，進(jìn)一步，。

我們發(fā)現(xiàn)，第 次可以得到 。

。

……

第 次，

第 次，。

第 次，。

第 次，。

先計(jì)算存儲(chǔ)下來(lái)再求值，不失為一種好方法；但亦可以在計(jì)算 的同時(shí)判斷 分解為 的冪（即轉(zhuǎn)為 進(jìn)制）后是否含 ，邊計(jì)算邊乘。

形式化地，對(duì)于 位，其代表的冪 為 （）。

這樣，我們由低位向高位計(jì)算，每次將底數(shù)平方即可。

下面兩份偽代碼，分別對(duì)應(yīng)這種方法的如上兩種實(shí)現(xiàn)。

function?power(a,?n):
?pow[0...log?n],?pow[0]?:=?1
?for?i:?1?to?inf
??if?(2^i?>?n)?break
??else?pow[i]?=?pow[i?-?1]^2
?res?:=?1
?for?i:?1?to?inf
??if?(2^i?>?n)?break
??else:
???if?(n?bitand?2^i)?res?=?res?*?pow[i]
?return?res
#?n?bitand?2^i?可理解為?n?在二進(jìn)制表示下含?2^i?位
function?power(a,?n):
?res?:=?1,?p?:=?a
?while?n?>?0:
??if?(n?bitand?1)?then?res?=?res?*?a
??p?=?p^2,?n?=?n?>>?1
?return?res
# bitand 表示按二進(jìn)制位與，>>?表示按二進(jìn)制位右移（可理解為除以 2 下取整）。
這樣的時(shí)間復(fù)雜度仍為 ，空間復(fù)雜度為 。

這種方法，就是平方求冪，也叫快速冪。

在一些其他的地方，也會(huì)用到這種思想。

比如：求 ，。

要知道，絕大部分語(yǔ)言中，能存儲(chǔ)的最大整數(shù)都只是 。如果我們直接計(jì)算，可能會(huì)自然溢出造成答案錯(cuò)誤。

這時(shí)，我們就想到平方求冪的思想。

我們考慮，，于是我們考慮通過(guò) 求出 。即：

function?times(a,?b,?m):
?if?b?=?0?then?return?0
?t?:=?times(a,?(b?-?b?mod?2)?/?2,?m)
?if?b?mod?2?=?1
?then:?return?((t? ?t)?mod?m? ?a?mod?m)?mod?m
?else:?return?(t? ?t)?mod?m
同樣地，也可以對(duì) 進(jìn)行二進(jìn)制拆分。

function?power(a,?b,?m):
?res?:=?0
?while?b?>?0:
??if?(b?bitand?1)?then?res?=?(res? ?a)?mod?m
??a?=?(a? ?a)?mod?m,?b?=?b?>>?1
?return?res
# bitand 表示按二進(jìn)制位與，>>?表示按二進(jìn)制位右移（可理解為除以 2 下取整）。
這樣，我們用 的時(shí)間復(fù)雜度算出了大數(shù)乘積取模的值。俗稱(chēng)“龜速乘”。

事實(shí)上，平方求冪的思想，在任何具有結(jié)合律的、參與運(yùn)算的數(shù)據(jù)相同的運(yùn)算中，都可以使用。

如矩陣乘法等。

好了，快速求冪的方法就講到這里，如果對(duì)你有哦幫助，歡迎點(diǎn)贊哦~~