高效计算大指数幂（Python快速幂算法详解）

什么是快速幂算法？

快速幂算法是一种利用二进制分解和分治思想来高效计算 a^b 的方法。其核心思想是：将指数 b 表示为二进制形式，然后通过不断平方底数、根据二进制位决定是否累乘，从而将时间复杂度从 O(b) 降低到 O(log b)。

举个例子

假设我们要计算 3^13：

• 13 的二进制是 1101
• 所以 3^13 = 3^(8+4+0+1) = 3^8 × 3^4 × 3^1
• 我们可以通过不断平方得到：3¹, 3², 3⁴, 3⁸
• 然后只把对应二进制位为1的项相乘即可

Python 快速幂算法实现

下面是不带取模的快速幂基础版本：

def fast_pow(base, exponent):    if exponent == 0:        return 1    result = 1    while exponent > 0:        # 如果当前指数是奇数，说明二进制最低位是1        if exponent % 2 == 1:            result *= base        # 底数平方，指数除以2（右移一位）        base *= base        exponent //= 2    return result# 测试print(fast_pow(3, 13))  # 输出: 1594323

快速幂取模（更实用的版本）

在实际编程竞赛或工程中，我们通常需要计算 (a^b) mod m，以防止结果过大溢出。这时只需在每一步都取模即可，这就是快速幂取模：

def fast_pow_mod(base, exponent, mod):    if mod == 1:        return 0    result = 1    base = base % mod  # 先对底数取模    while exponent > 0:        if exponent % 2 == 1:            result = (result * base) % mod        exponent = exponent // 2        base = (base * base) % mod    return result# 测试print(fast_pow_mod(3, 13, 1000))  # 输出: 323

为什么快速幂这么快？

普通幂运算需要做 b-1 次乘法，而快速幂每次都将指数减半，因此最多只需要做 log₂(b) 次循环。例如，计算 a^1000000，普通方法要做近百万次乘法，而快速幂只需约20次！这就是高效幂运算的魅力。

总结

通过本教程，你已经掌握了 Python快速幂算法 的基本原理和实现方式。无论是基础版还是带取模的版本，都能极大提升大指数幂运算的效率。这项技术在算法竞赛、密码学（如RSA）、大数据处理等领域都有广泛应用。

记住关键词：Python快速幂算法、快速幂取模、高效幂运算、Python算法教程。多加练习，你也能写出高效的代码！