Golang實現快速求冪的方法詳解
今天講個有趣的算法:如何快速求nm,其中n和m都是整數。
為方便起見,此處假設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快速求冪內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- Golang中slice刪除元素的性能對比
- GoLang sync.Pool簡介與用法
- Golang切片刪除指定元素的三種方法對比
- golang 刪除切片的某個元素及剔除切片內的零值方式
- Golang 正則匹配效率詳解