在四则运算的基础上,朴素算法计算$x^a$是将$x$连乘$a$次,算法时间复杂度为$O(n)$, 而快速幂算法可以优化到$O(logn)$,效率得到极大提升,而且可以推广到矩阵幂运算上。

例如我们想计算$5^{10}$的值。 首先有一个显然的事:任何整数都可以用二进制表示,也就是说,任何整数都可以按 2 的升幂展开,我们把指数$10$展开, $10 = (1010)_2$即

\[10 = 0\times2^0 + 1\times2^1+ 0\times2^2 + 1\times2^3\]

考虑到$x^{ab} = ({x^b})^a$,于是:

\[\begin{aligned} 5^{10} &= 5^{(0\times2^0 + 1\times2^1+ 0\times2^2 + 1\times2^3)}\\ &={(5^{2^0})}^0 \times {(5^{2^1})}^1 \times {(5^{2^2})}^0 \times {(5^{2^3})}^1\\ &=5^0 \times {25}^1 \times {625}^0 \times {390625}^1 \end{aligned}\]

$5$的平方是$25$,$25$的平方是$625$,$625$的平方是$390625$,整个式子的计算只需要 1 次乘法和 3 次平方 ($5^0$和${625}^0$都是 1 不用参与乘法计算),原来 10 次计算就被我们简化到 4 次运算。

不失一般性,把$x^a$中指数$a$按 2 的升幂展开:

\[a = a_0\times2^0 + a_1\times2^1 + a_2\times2^2 + a_3\times2^3 + \dots + a_n\times2^n\]

指数$a$用这个展开式代替,即:

\[\begin{aligned} x^a &= x^{ a_0\times2^0 + a_1\times2^1 + a_2\times2^2 + a_3\times2^3 + \dots + a_n\times2^n }\\ &=({x^{2^0}})^{a_0} \times ({x^{2^1}})^{a_1} \times ({x^{2^2}})^{a_2} \times \dots \times ({x^{2^n}})^{a_n}\\ &=(x)^{a_0} \times ({x^2})^{a_1} \times ({x^4})^{a_2} \times \dots \times ({x^{2^n}})^{a_n} \end{aligned}\]

式子$(x)^{a_0} \times ({x^2})^{a_1} \times ({x^4})^{a_2} \times \dots \times ({x^{2^n}})^{a_n}$ 并不复杂。

  • 括号里面第一项是$x$,第二项是$x^2$,第三项是$x^4$,即后一项都是前一项的平方,迭代平方即可;

  • $a_0,a_1,a_2,\dots ,a_n$来自指数$a$的二进制拆解,它们要么是$0$要么是$1$。 如果$a_i$为$0$,那么$({x^{2^i}})^{a_i}$就是$1$,不用参与连乘计算。 如果$a_i$为$1$,那么$({x^{2^i}})^{a_i}$就是${x^{2^i}}$,即迭代平方的结果。

// 求 x 的 k 次方的值
int quickpow(int x, int k)
{
	int res = 1;//连乘结果
	for (; k; k /= 2)//对k进行二进制拆解
	{
		if (k & 1)//ai为1才参与运算,ai为0不用参与计算
		{
			res *= x;
		}
		x *= x;//迭代平方
	}
	return res;
}

文章为 C#.NAME 原创,禁止转载。