快速幂算法

原理

例子

计算。

可以看到，原本需要12次乘法的计算，现在只需要5次乘法了。

分析

将的上标全写为二进制

可以看到，完全展开之后，的上标组成的二进制串正是的二进制串。真正进行计算时，可以省略。因此，用快速幂算法计算时，需要进行次平方运算和次乘法运算，其中是的二进制位数，是的二进制中的的个数。平方运算其实就是乘法运算，因此，需要进行的乘法运算次数总计为，介于倍之间。因此，快速幂算法的时间复杂度为

实现

def exp1(x, n):
    if n == 0:
        return 1
    if n == 1:
        return x
    y = exp1(x, n>>1) ** 2
    if n & 0x1:
        y *= x
    return y

测试

快速幂算法还可以像下面这样表述，时间复杂度与上面的一致。不过测试表明，比上面的要慢。

def exp2(x, n):
    if n == 0:
        return 1
    if n == 1:
        return x
    y = exp2(x*x, n>>1)
    if n & 0x1:
        y *= x
    return y

两种快速幂算法的比较

可以看到，尽管大数乘法并非，快速幂算法依然要比普通算法快得多。