Quick Pow: 如何快速求幂


今天讲个有趣的算法:如何快速求 /(n^m/),其中 n 和 m 都是整数。

为方便起见,此处假设 m >= 0,对于 m < 0 的情况,求出 /(n^{|m|}/) 后再取倒数即可。

另外此处暂不考虑结果越界的情况(超过 int64 范围)。

当然不能用编程语言的内置函数,我们只能用加减乘除来实现。

n 的 m 次方的数学含义是:m 个 n 相乘:n*n*n…*n,也就是说最简单的方式是执行 m 次乘法。

直接用乘法实现的问题是性能不高,其时间复杂度是 O(m),比如 /(3^{29}/) 要执行 29 次乘法,而乘法运算是相对比较重的,我们看看能否采用什么方法将时间复杂度降低。

设 m = x + y + z(x、y、z 都是整数),我们知道有如下数学等式: /(n^m/) = /(n^{x+y+z}/) = /(n^x * n^y * n^z/)。

也就是说,如果我们已经知道 /(n^x/)、/(n^y/)、/(n^z/) 的值,是不是就可以直接用他们相乘得出 /(n^m/)的结果?这样的话乘的次数就大大降低了。

于是问题就变成应该将 m 拆成怎样的几个数的和。

因为计算机是玩二进制的,我们尝试着将这些数跟 2 扯上联系(以 2 为底),看看会不会有奇迹发生。

我们看看具体的例子:/(3^{29}/)。

我们将 29 做这样的拆分:29 = 16 + 8 + 4 + 1。

这个拆分有什么特点呢?右边的数都是 2 的 X 次方(/(2^4 + 2^3 + 2^2 + 2^0/))。

我们把上面的拆分带进公式:/(3^{29} = 3^{16} * 3^{8} * 3^{4} * 3^{1}/)。

那我们能不能知道 /(3^{16}/)、/(3^{8}/)、/(3^{4}/)、/(3^{1}/) 是什么呢?

我们不用计算就知道 /(3^{1}/) 是什么——但仅此而已。

不过我们可以用 /(3^{1}/) 自乘 4 次的到 /(3^4/);然后再用 /(3^4/) 自乘得到 /(3^8/);再通过 /(3^8/) 自乘得到 /(3^{16}/)。

好像有点感觉了——我们每做一次乘法,就能将结果翻倍(如 /(3^4/) 自乘就变成 /(3^4*3^4 = 3^8/))。

如此,虽然也要多次乘法,但乘的次数从 29 次降到 9 次!

然后我们再回头看看上面的拆分:

29 = 16 + 8 + 4 + 1 = /(2^4 + 2^3 + 2^2 + 2^0/) = /(1*2^4 + 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0/) 。

这不就是学校学的二进制转十进制吗(29 的二进制是 11101)?

/(3^{29} = 3^{16} * 3^{8} * 3^{4} * 3^{1}/) 是说:取 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 算法代替语言内置的浮点函数。

Quick Pow: 如何快速求幂

原创文章,作者:506227337,如若转载,请注明出处:https://blog.ytso.com/270753.html

(0)
上一篇 2022年6月30日
下一篇 2022年6月30日

相关推荐

发表回复

登录后才能评论