快速幂运算简介

快速幂运算是一种高效计算整数幂的方法，通过将幂指数分解为二进制形式，减少乘法次数，从而提高计算速度。它广泛应用于计算机科学中的加密算法和数值计算。

前言

在计算机科学中，幂指数的计算是一个常见的任务，尤其在加密算法和数值计算中。传统的计算方法通常使用循环或递归来实现。例如，要计算 $a^b$，可以使用以下代码：

1
2
3
4
5
def power(a, b):
    result = 1
    for i in range(b):
        result *= a
    return result

这种方法的时间复杂度为 $O(b)$，当 $b$ 非常大时，计算效率较低。

快速幂运算的原理

快速幂运算通过将幂指数 $b$ 分解为二进制形式来减少计算次数。例如，若 $b = 13$，其二进制表示为 $1101$，则 $a^{13}$ 可以表示为 $a^{1101} = a^{8} \times a^{4} \times a^{1}$。在计算过程中，我们只需计算 $a^1$、$a^2$、$a^4$ 和 $a^8$，而不需要计算所有中间幂次。
用十进制的方式表现， $a^{13}$ = $a^8 \times a^4 \times a^1$。
用二进制的方式表现， $a^{1101}$ = $a^{1000} \times a^{100} \times a^1$。

这种方法的核心思想是利用二进制位的性质：每个二进制位代表一个幂次的乘积是否参与最终结果。通过这种方式，快速幂运算将时间复杂度从 $O(b)$ 降低到 $O(\log b)$，大大提高了计算效率。

快速幂运算的实现

下面是使用Python实现快速幂运算的代码：

1
2
3
4
5
6
7
8
def power(a, b):
    result = 1
    while b > 0:
        if b % 2 == 1:
            result *= a
        a *= a
        b >>= 2
    return result

这段代码中，我们使用了一个循环来遍历幂指数 $b$ 的二进制位。在每一次循环中，我们检查当前位是否为1，如果是，则将 $a$ 累乘到结果中。然后，我们将 $a$ 平方，并将幂指数右移一位，以处理下一个二进制位。
通过这种方式，我们可以在 $O(\log b)$ 的时间复杂度内计算出 $a^b$ 的值。

让我们来模拟一下快速幂运算的过程。假设我们要计算 $a^{27}$，其二进制表示为 $11011$。

1
2
3
4
5
6
7
8
9
10
11
首先b = 27, result = 1
进入第一次循环，此时最低位为1，所以 result *= a , result = a , a *= a , a = a^2 , 幂指数右移一位，b = 13

第二次循环，最低位为1，所以 result *= a^2 , result = a^3 , a *= a , a = a^4 , 幂指数右移一位，b = 6

第三次循环，最低位为0，所以不改变 result , a *= a , a = a^8 , 幂指数右移一位，b = 3

第四次循环，最低位为1，所以 result *= a^8 , result = a^11 , a *= a , a = a^16 , 幂指数右移一位，b = 1

第五次循环，最低位为1，所以 result *= a^16 , result = a^27 , 幂指数右移一位，b = 0
循环结束，最终结果为 a^27

在上面这次的模拟中，我们可以看到，通过五次循环，我们成功地计算出了 $a^{27}$ 的值。这种方法大大减少了乘法的次数，提高了计算效率。

快速幂运算的应用

快速幂运算在计算机科学中有广泛的应用，特别是在加密算法和数值计算中。例如，在许多统计题目中我们会对$10^{9}+ 7$
下面我们演示计算$2^{20} mod 10^{9}+ 7$

1
2
3
4
5
6
7
8
def power(a, b, mod):
    result = 1
    while b > 0:
        if b % 2 == 1:
            result = (result * a) % mod
        a = (a * a) % mod
        b >>= 1
    return result

这段代码中，我们在每一步计算中都对结果取模，以防止结果过大导致溢出。
对于一些特别大的幂，比如 $2^{1000000000}$，我们可以使用欧拉降幂的方法来优化计算。

本文章发布于 hjq.college，转载请注明出处。