本節書摘來自華章計算機《算法基礎》一書中的第2章，第2.3節，作者：（美）羅德·斯蒂芬斯（Rod Stephens）著，更多章節內容可以訪問云棲社區“華章計算機”公眾號查看

2.3　求冪運算

有時程序需要計算某數的正整數次冪，這在該冪指數不大時容易完成。例如，73可以通過計算7×7×7很容易地得到結果343。對于較大的冪，例如7102×187×291，這種計算過程是十分緩慢的。
注　計算較大的冪如7102×187×291可能很緩慢。但如果不是這種求冪運算在某些重要密碼學中得到應用，人們也許不會十分關心它。
幸運的是，有一種較快的方法來執行這種運算。這種方法基于乘方運算的兩個關鍵法則：

當這個冪是二次冪時，第一個法則可以迅速地計算出A的冪。
第二個法則能將這些A的冪結合以產生想要的結果。
以下偽代碼展示了這個算法：

例如要計算出76。首先算法計算出71、72、74。由于下一個指數8比所需的6大，因此算法停止。

接下來算法使用第二個法則來從已經產生的二次冪中生成76。如果將6看作2的冪的和，6＝2＋4。使用第二個法則，得到76＝72×74＝49×2 401＝117 649。
執行這個運算進行兩次乘法來計算72和74再加上一次乘法來獲得最終結果，即總共進行三次乘法運算。這比簡單計算7×7×7×7×7×7進行了更少的乘法運算，但在本例中這只是一個小小的不同。
更普遍地，對于指數P，算法進行log(P)次運算來得到A的P次冪。然后算法檢驗A的二進制位數來確定它應當將其中的哪些乘在一起以獲得最終結果。（如果P的二進制位數是1，那么最終的結果應當包含2的相應冪。在前例中，6的二進制表示是110，因此需要計算2的二次冪和四次冪，即22和24。）
在二進制中，數值P有log2(P)位，因此總共的運行時間復雜度是O(log P)＋O(log P)＝O(log P)。即使P為一百萬，log(P)大約只有20，因此這個算法需運行20步左右(至多40次乘法)。這比一百萬要小得多。
這種算法的一個限制是當指數很大時，冪增長得過快。即使一個如7300這樣“小”的值也有254個十進制位。這意味著用來計算大指數冪龐大數相乘的過程是緩慢的，并且需要大量計算空間。
幸運的是，這種龐大的冪運算的最常見應用是加密算法，這種算法的運算限制在某個模中。盡管這個模通常較大，但仍能限制住運算數和結果的大小。例如如果某模有100位，兩個100位數的積就不會大于200位。那么，接下來可以再次用這個模來得到一個不大于100位的結果。雖然用模將每一個數減小使得每步運算稍微變慢，但也意味著可以計算幾乎無限大的值。

總結

以上是生活随笔為你收集整理的《算法基础》——2.3　求幂运算的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。