1.1 二进制快速幂

  假设有这么一个需求，要求计算出3的100次方，该怎么优化算法，减少运算量？很明显，如果使用动态规划思想，我们知道这里面包含了大量重复运算，根本不需要99次乘法。比如我们可以使用49次乘法算出3⁵⁰,再平方一下，也就是多一次乘法运算，那么就是50次乘法就计算出了结果。
  好了，算法思想已经get到了，那么我们就继续想想，如果继续简化，简化到不能简化为止。也许聪明的读者已经想到了。那么就是先一次乘法，平方一下，计算出3²,存入数组。然后再计算3⁴，3⁸，3¹⁶，3³²,3⁶⁴。然后把100组合一下，100=64+32+4。也就是3¹⁰⁰=3⁶⁴*3³²*3⁴.
  总共使用了几次乘法呢？总共使用了8次乘法，计算3²，3⁴，3⁸，3¹⁶，3³²，3⁶⁴用了5次。计算3⁶⁴*3³²*3⁴用了3次。这种用少量乘法次数，计算指数的算法被称为二进制快速幂（Binary Exponentiation）。
  但是再仔细想想，其实连数组都不需要的。我们这样计算：
$$\begin{gathered} p=3^2 \\ r=1 \\ p=3^4 \\ r=3^4 \\ p=3^8 \\ r=3^4 \\ p=3^{16} \\ r=3^4 \\ p=3^{32} \\ r=3^{36} \\ p=3^{64} \\ r=3^{100} \end{gathered}$$
  明白了原理后，代码就非常简单了，以下是python代码：

# _*_ coding:utf-8 _*_
# _*_ coding:utf-8 _*_
def binary_exponentiation(base, power):
    power_2 = 1
    r = 1
    p = base
    while power_2 <= power:
        if power_2 & power != 0:
            r *= p
        p = p * p
        power_2 = power_2 << 1
    return r


if __name__ == '__main__':
    print(binary_exponentiation(3, 100))
    print(3 ** 100)

    print(binary_exponentiation(32, 15))
    print(32 ** 15)

测试结果：

515377520732011331036461129765621272702107522001
515377520732011331036461129765621272702107522001
37778931862957161709568
37778931862957161709568