python 实现大数乘方

本算法目的是计算 $x^n$ 。当 $n$ 很大时，按常规算法从头到尾乘下去非常消耗计算资源，算法的时间复杂度为 $O(n)$ ，而本算法可以将时间复杂度降为 $O(\mathrm{log}n)$ 。

这个问题可以这样想：如果将 $x^n$ 转换为 $(x^{n/2})\cdot(x^{n/2})$ ，那么我们只需要计算 $\frac{n}{2}+1$ 次乘法即可。再进一步，如果将原式转换为 $(x^{n/4})^4$ ，那么只需要计算 $\frac{n}{4}+4$ 次乘法，对于 $n$ 比较大的情况，无疑可以大大节约乘法的次数。
当 $n$ 恰好为 2 的整数次幂时：
$x^2 = x\cdot x$
$x^4 = (x\cdot x)^2$
$x^8 = ((x\cdot x)^2)^2$
$x^{16}=(((x\cdot x)^2)^2)^2$

现在的问题是， $n$ 并不恰好是 2 的整数次幂。那么对于更一般的情况，应该怎么处理呢？

我们隐约可以想到，这和 $n$ 的二进制表示相关。不妨设 $n=21$ ，其二进制为 10101，将其从左到右，转化成十进制：
左侧第一位是 1 故对应 1，
往右移动一位，10 对应的是1*2+0*1，
再往右移动一位 101 对应的是 (1*2+0*1)*2+1，
再往右移动一位，1010 对应的是 ((1*2+0*1)*2+1)*2+0*1，
移动到最右端，10101 对应的是 (((1*2+0*1)*2+1)*2+0*1)*2+1
我们可以轻松掌握规律：每增加一位，现有的数据就乘以2，同时，新增的那一位如果是1，则需再加1。

而 $n$ 是指数项，指数项乘以2，对应的是幂的平方，指数项加1，对应的是幂乘以一次底数。即：
$\begin{align*} x^{21}&=x^{10101_b}\\ &=(x^1)^{0101_b} \\ &=((x^1)^2)^{101_b}\\ &=(((x^1)^2)^2x)^{01_b} \\ &=(((((x^1)^2)^2x))^2)^{1_b}\\ &=(((((x^1)^2)^2x))^2)^{2}x \end{align*}$

因此，我们的算法只需要将 $n$ 转为二进制，然后从左到右遍历各位二进制数，每增加一位，将当前值做平方，同时观察该位二进制值，如果是1，再将当前值乘以底数，反复迭代，即可得到最终结果。

网上大部分的代码采用的算法都是递归，本算法采用循环的形式：

def pow(x, n):
    x_init = x
    bin = []
    while n>0:
        r = n%2
        bin.insert(0, r)
        n = n//2

    for idx in range(1, len(bin)):
        x = x*x
        if bin[idx]==1:
            x = x*x_init
    return x

python 实现大数乘方

推荐阅读更多精彩内容