如何快速算出一個數(shù)的n次方？

投稿作者 OIer，目前對計算機及算法的了解主要在信息學競賽方面。

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

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

一般來說，我們要求 ，只需要將 乘 次即可，時間復雜度為 。

但有時， 極大，這種方法需要的時間開銷是不可接受的。

比如，求 。

如果我們直接計算多個這樣的式子，至少在目前主流計算機中，所用時間以分鐘計。

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

以計算 為例。

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

于是我們想到一種方法：先計算 ，

再計算 。

這樣，我們就可以通過把 分解為約 個大小為 的塊，將時間復雜度由 降為 。

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

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

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

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

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小為原來的一半，這種方法的時空復雜度是 。

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

第一次乘法，只能計算 。

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

第三次，進一步，。

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

。

……

第 次，

第 次，。

第 次，。

第 次，。

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

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

這樣，我們由低位向高位計算，每次將底數(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?在二進制表示下含?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 表示按二進制位與，>>?表示按二進制位右移（可理解為除以 2 下取整）。
這樣的時間復雜度仍為 ，空間復雜度為 。

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

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

比如：求 ，。

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

這時，我們就想到平方求冪的思想。

我們考慮，，于是我們考慮通過 求出 。即：

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
同樣地，也可以對 進行二進制拆分。

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 表示按二進制位與，>>?表示按二進制位右移（可理解為除以 2 下取整）。
這樣，我們用 的時間復雜度算出了大數(shù)乘積取模的值。俗稱“龜速乘”。

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

如矩陣乘法等。

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