溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了Golang怎么實現快速求冪的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Golang怎么實現快速求冪文章都會有所收獲，下面我們一起來看看吧。
為方便起見，此處假設m>=0，對于m< 0的情況，求出n|m|后再取倒數即可。
另外此處暫不考慮結果越界的情況（超過 int64 范圍）。
當然不能用編程語言的內置函數，我們只能用加減乘除來實現。
n的m次方的數學含義是：m個n相乘：n*n*n...*n，也就是說最簡單的方式是執行 m 次乘法。
直接用乘法實現的問題是性能不高，其時間復雜度是 O(m)，比如 329要執行29次乘法，而乘法運算是相對比較重的，我們看看能否采用什么方法將時間復雜度降低。
設m = x + y + z（x、y、z 都是整數），我們知道有如下數學等式： nm= nx+y+z = nx∗ny∗nz。
也就是說，如果我們已經知道 nx、ny、nz的值，是不是就可以直接用他們相乘得出 nm的結果？這樣的話乘的次數就大大降低了。
于是問題就變成應該將 m 拆成怎樣的幾個數的和。
因為計算機是玩二進制的，我們嘗試著將這些數跟 2 扯上聯系（以 2 為底），看看會不會有奇跡發生。
我們看看具體的例子：329。
我們將29做這樣的拆分：29 = 16 + 8 + 4 + 1。
這個拆分有什么特點呢？右邊的數都是 2 的 X 次方（24+23+22+20）。
我們把上面的拆分帶進公式：329=316∗38∗34∗31。
那我們能不能知道 316、38、34、31是什么呢？
我們不用計算就知道31是什么——但僅此而已。
不過我們可以用 31自乘 4 次的到34；然后再用 34自乘得到38；再通過38自乘得到316。
好像有點感覺了——我們每做一次乘法，就能將結果翻倍（如 34自乘就變成 34∗34=38）。
如此，雖然也要多次乘法，但乘的次數從29次降到9次！
然后我們再回頭看看上面的拆分：
29 =16+8+4+1=24+23+22+20= 1∗24+1∗23+1∗22+0∗21+1∗20。
這不就是學校學的二進制轉十進制嗎（29 的二進制是 11101）？
329=316∗38∗34∗31是說：取 29 的二進制表示中所有值是 1 的位，算出它們的指數值并相乘就得到最終的值。
我們用 go 語言實現一下：
// 求 a 的 n 次方
// a、n 是非負整數
func Pow(a,n int64) int64 {
// 0 的任何次方都是 0
if a == 0 {
return 0
}
// 任何數的 0 次方都是 1
if n == 0 {
return 1
}
// 1 次方是它自身
if n == 1 {
return a
}
// 用滾雪球的方式計算冪
// 雪球初始值是 1
var result int64 = 1
// 滾動因子初始化為 a 的 1 次方（a 自身）
factor := a
// 循環處理直到 n 變成 0（所有的二進制位都處理完了）
for n != 0 {
// 跟 1 做與運算，判斷當前要處理的位是不是 1
// 之所以是直接跟 1 做與運算，因為后面每處理一輪都將 n 右移了一位，保證每次要處理的位都在最低位
if n & 1 != 0 {
// 當前位是 1，需要乘進去
result *= factor
}
// 每輪結束時將滾動因子自乘
// 因為每行進一輪，指數都翻倍，整體結果就是自乘
// 比如本輪因子是 2**4，下一輪就是 2**8
// 2**8 = 2**(4+4) = 2**4 * 2**4
// （** 表示指數）
factor *= factor
// n 右移一位，將下一輪要處理的位放在最低位
n = n >> 1
}
return result
}有什么用呢
很多語言內置的 pow 函數都只接受浮點數，浮點數的運算是非常重的，如果我們的程序需要頻繁計算整數的冪，就可以采用 quick pow 算法代替語言內置的冪函數以提升性能。
我們對 go 語言內置的 math.Pow 和 quick pow 算法做個性能測試對比一下。
// 測試 3 的 29 次方的性能測試
var benchPowB int64 = 3
var benchPowP int64 = 29
// 上面的 quick pow 算法
func BenchmarkQuickPow(b *testing.B) {
for i := 0; i < b.N; i++ {
algo.Pow(benchPowB, benchPowP)
}
}
// go 語言 math 包的 Pow 方法，只接受 float64 類型
func BenchmarkInnerPow(b *testing.B) {
x := float64(benchPowB)
y := float64(benchPowP)
for i := 0; i < b.N; i++ {
math.Pow(x, y)
}
}
// 用簡單乘法實現（3 自乘 29 次）
func BenchmarkSimpleMulti(b *testing.B) {
for i := 0; i < b.N; i++ {
var r int64 = 1
var j int64 = 0
for ; j < benchPowP; j++ {
r *= benchPowB
}
}
}測試結果：
goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz
BenchmarkQuickPow-8 357897716 3.373 ns/op
BenchmarkInnerPow-8 39162492 29.30 ns/op
BenchmarkSimpleMulti-8 121066731 9.549 ns/op
PASS
ok command-line-arguments 4.894s
從性能測試結果看，quick pow 算法比簡單乘法快了好幾倍，比 math.pow 快了近 10 倍。
所以，如果程序只需要求整數冪，而且能確保計算結果不會越界時，可以考慮使用 quick pow 算法代替語言內置的浮點函數。
關于“Golang怎么實現快速求冪”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Golang怎么實現快速求冪”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
