引出问题

在计算机科学中，幂运算是一种非常常见且基础的操作，尤其是在涉及到大数运算时，幂运算的效率对整个计算过程至关重要。设想以下场景：

1. 在加密算法中，如 RSA 算法，常常需要计算大数的幂，且这种计算必须在一定时间内完成，以确保安全性。
2. 在数值计算中，我们可能需要反复进行大规模的幂运算，如果采用最直接的计算方法，其计算量和时间将非常庞大。

如果我们采用朴素的计算方法，例如计算 $a^b$ 时，通过不断相乘 $a$ 来获得结果，其时间复杂度为 $O(b)$。当 $b$非常大时，这种方法显然是不可行的。为此，我们需要一种更加高效的算法来解决这个问题，快速幂算法就是这样一种高效的算法。

快速幂算法原理

快速幂算法的核心思想是通过将幂指数拆分为二进制形式，并通过一系列的乘法和平方操作，来高效地计算幂次。它主要依赖两个关键概念：

1. 二进制拆分：任何一个整数 $b$ 都可以表示为一系列二进制位的组合，即：

   $$b=b_k\times 2^k+b_{k-1}\times 2^{k-1}+\cdots +b_1\times 2^1+b_0\times 2^0$$

   其中 $b_i$为二进制位（0或1）。通过这一表示，可以将幂运算转化为多个乘法和平方操作。

   举例说明：

   假设我们要计算 $3^{13}$，首先我们将 13 表示为二进制形式，即 $13={1101}_2$。根据二进制拆分的原则，我们可以将幂运算拆解为：

   $$3^{13}=3^{(1\times 2^3+1\times 2^2+0\times 2^1+1\times 2^0)}=3^{2^3}\times 3^{2^2}\times 3^{2^0}$$

   这种拆分将幂运算转化为多次乘法和平方操作，虽然差拆分后的项也是幂，但是这些项彼此之间也是有关系的，可以用较小的计算量算出，因此有助于提高计算效率。

2. 霍纳法则：霍纳法则是一种高效计算多项式的方法，能够有效减少乘法运算次数。在快速幂算法中，霍纳法则可以帮助我们进一步简化幂运算的过程。我们可以将幂指数的二进制表示进行逐步计算，而不是一次性完成。根据霍纳法则，了可以进一步变换成

   $$b=((\dots (b_k\times 2^1+b_{k-1})\times 2+\dots )\times 2+b_1)\times 2+b_0$$

   那么就有

   $$a^b=a^{((\dots (b_k\times 2^1+b_{k-1})\times 2+\dots )\times 2+b_1)\times 2+b_0}=(\dots ((a^{b_k}{)}^2\times a^{b_{k-1}}{)}^2\cdots \times a^{b_1}{)}^2\times a^{b_0}$$

3. 从左到右的快速幂算法

从左到右的快速幂算法也就是刚才通过霍纳法则导出来的公式

通过依次读取幂指数 $b$的二进制表示，从高位到低位逐步构建幂运算的结果。在每读取一位时，首先将当前的结果进行平方，然后根据该位是否为1来决定是否乘以基数$a$。这种方式避免了重复计算，使得时间复杂度降低到$O(\log b)$。

算法步骤：

1. 初始化结果为1。
2. 从左到右扫描 $b^{}$ 的二进制表示（从最高位到最低位）。
3. 对于每一位：
   • 先将当前结果平方。
   • 如果该位为1，则结果乘以基数 $a^{}$。
4. 最终的结果即为 $a^b$。

代码实现：

def quick_pow_from_left_to_right(a, b):
    # 将整数b转换为二进制字符串，并去除前缀'0b'
    b = bin(b)[2:]
    # 初始化答案为1，因为幂次最低为0，任何数的0次幂都是1
    ans = 1
    # 遍历b的二进制表示中的每一位
    for b_i in b:
        # 每遇到一个二进制位，都需要平方之前的结果
        ans *= ans
        # 如果当前二进制位是1，则需要将a累乘到答案中
        if b_i == '1':
            ans *= a
    # 返回最终的计算结果
    return ans

运行原理：

假设 $b=13$（即二进制表示为 1101），我们想计算 $a^{13}$。从左到右读取其二进制表示：

• 第1位是1，结果先平方，再乘以 $a^{}$。
• 第2位是1，结果再平方，再乘以 $a^{}$。
• 第3位是0，结果只平方，不乘以 $a^{}$。
• 第4位是1，结果再平方，再乘以 $a^{}$。

4. 从右到左的快速幂算法

与从左到右的算法不同，从右到左的算法从幂指数的最低位开始读取二进制位。每次读取一位后，决定是否将当前的基数乘到结果上，然后将基数平方，为下一次迭代做准备。这个过程是直接利用了二进制拆分的公式，所以理解起来非常的直观

算法步骤：

1. 初始化结果为1，当前基数为 $a^{}$。

2. 从右到左扫描 $b^{}$ 的二进制表示（从最低位到最高位）。

3. 对于每一位：

   • 如果该位为1，将当前基数乘到结果上。
   • 将基数平方。

4. 最终的结果即为 $a^b$。

代码实现：

def quick_pow_from_right_to_left(a, b):
    # 将整数b转换为反转二进制字符串，并去除前缀'0b'
    b = reversed(bin(b)[2:])
    # 初始化答案为1，即a的0次方
    ans = 1
    # 遍历b的二进制每一位
    for b_i in b:
        # 如果当前位为1，将当前结果与a的平方累乘
        if b_i == '1':
            ans *= a
        # 每遍历一位，将底数a平方
        a *= a
    # 返回计算结果
    return ans

运行原理：

同样以 $b=13$（二进制为1101）为例，从右到左的计算步骤如下：

• 第1位是1，结果乘以 $a^{}$，基数平方。
• 第2位是0，基数平方。
• 第3位是1，结果乘以平方后的基数，基数平方。
• 第4位是1，结果再乘以平方后的基数，最终得到结果。

通过这种方式，我们避免了不必要的计算，快速得出了 $a^{\mathrm{13}}$ 的结果。

5. 复杂度分析

快速幂算法的时间复杂度为 $O(\log b)$，无论是从左到右还是从右到左。相比于朴素的 $O(b)$ 复杂度，这种方法在处理大幂次计算时显著提高了效率。

我将几种方法放在一起进行一个对比

a = 2
b = 1000000

print('从左到右快速幂')
t = time.time()
quick_pow_from_left_to_right(a, b)
print(time.time() - t)

print('从右到左快速幂')
t = time.time()
quick_pow_from_right_to_left(a, b)
print(time.time() - t)

print('朴素幂')
t = time.time()
pow_(a, b)
print(time.time() - t)

print('库函数')
t = time.time()
pow(a, b)
print(time.time() - t)

运行结果如下：

从左到右快速幂
0.0029942989349365234
从右到左快速幂
0.005053997039794922
朴素幂
18.3477623462677
库函数
0.0029935836791992188

可以发现在大指数时，快速幂的效果非常明显，并且根据运行时间推断，python内置的pow函数应该也是快速幂算法的变种。
关于 从左到右和从右到左哪一种方法效率更高，在不同的平台应该有不同的表现，不过差异不大，选择喜欢的用即可

6. 总结

快速幂算法通过将幂次的二进制表示与逐步的平方、乘法操作结合起来，实现了高效的幂运算。无论是从左到右还是从右到左的实现，都大大减少了计算所需的时间，特别是在需要处理大数幂运算的场景下。掌握这种算法，对提升计算效率具有重要意义。