快速幂算法

2019-12-15 本文已影响0人 ABleaf

原理

$x^n = \begin{cases} {(x ^ \frac{n}{2})^2,} & 如果n是偶数\\ {x(x ^ \frac{n-1}{2})^2,} & 如果n是奇数\\ \end{cases}$

例子

计算 $x^{13}$ 。
$\begin{aligned} x^{13} &= (x^6)^2 \times x \\ &= ((x^3)^2)^2 \times x\\ &= ((x^2\times x)^2)^2\times x \end{aligned}$
可以看到，原本需要12次乘法的计算，现在只需要5次乘法了。

分析

将 $x$ 的上标全写为二进制
$\begin{aligned} x^{1101} &= (x^{110})^2 \times x^1 \\ &= ((x^{11})^2 \times x^0)^2 \times x^1\\ &= (((x^{1})^2\times x^1)^2 \times x^0)^2\times x^1 \end{aligned}$

可以看到，完全展开之后， $x$ 的上标组成的二进制串正是 $n$ 的二进制串。真正进行计算时， $\times x^0 = \times 1$ 可以省略。因此，用快速幂算法计算 $x^n$ 时，需要进行 $L - 1$ 次平方运算和 $C - 1$ 次乘法运算，其中 $L$ 是 $n$ 的二进制位数， $C$ 是 $n$ 的二进制中的 $1$ 的个数。平方运算其实就是乘法运算，因此，需要进行的乘法运算次数总计为 $L + C - 2$ ，介于 $1 \sim 2$ 倍 $\log_2(n)$ 之间。因此，快速幂算法的时间复杂度为
$T(n) = O(\log_2n)$

实现

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

测试

快速幂算法还可以像下面这样表述，时间复杂度与上面的一致。不过测试表明，比上面的要慢。
$x^n = \begin{cases} {(x ^ 2)^\frac{n}{2},} & 如果n是偶数\\ {x(x ^ 2)^\frac{n-1}{2},} & 如果n是奇数\\ \end{cases}$

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

两种快速幂算法的比较

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

快速幂算法

原理

例子

分析

实现

测试

猜你喜欢

热点阅读