快速幂算法|祀梦的个人博客

简介

快速幂算法是用于快速计算 a^b \enspace mod \enspace c的算法，可以用于快速的处理大整数幂的场景。

最简单的 for 循环求数字的 n 次幂需要 O(n) 的时间复杂度。快速幂方法可以达到 O（logN）的时间复杂度。

快速幂的核心思想是将指数拆分，以达到快速计算的目的。

二进制法的核心思想是将指数转换为二进制形式，通过逐位处理并结合平方运算减少乘法次数。

二进制分解指数
将指数 n 表示为二进制形式，例如 n=13 对应二进制为 1101，即 13=8+4+1=23+22+20。
幂的拆分
根据二进制分解，an=a2k×a2k−1×⋯×a20，其中仅当二进制位为 1 时，对应项被保留。
逐位处理与平方加速
- 从最低位到最高位依次处理二进制每一位。
- 若当前位为 1，则将当前的底数累乘到结果中。
- 每一步将底数平方，为处理更高位做准备。

def power(base,exp):
    res = 1
    while exp > 0:
        if exp & 1:
            res *= base
        base *= base
        exp >>= 1
    return res

折半法的核心公式如下

我们要快速计算 a 的 n 次方

当 n 为奇数的时候 a^n = a^{n/2} \ \times \ a^{n/2} \ \times \ a（还有一种方法是 a^n = a^{n-1} \ \times \ a）
当 n 为偶数的时候 a^n = a^{n/2} \ \times \ a^{n/2}
当 n 为 0 的时候，直接返回 1

通过递归或迭代，将大指数问题分解为小指数问题，最后合并结果。

def power(base, exp):
    if exp == 0: return 1
    half = power(base, exp//2)
    return half * half * (base if exp%2 else 1)

两者都可以实现在指数时间解决问题，二进制方法比折半法更加的省空间。