第76天：Python 二进制指数法 – O(log n) 快速幂计算（不使用内置函数）

Source: Dev.to

快速幂函数概述

函数设计：负指数和基准情况

def fast_power(x: float, n: int) -> float:
    """Return x raised to the power n using binary exponentiation."""
    if n == 0:
        return 1.0                     # base case: x⁰ = 1

    if n < 0:
        x = 1 / x
        n = -n

    result = 1.0
    while n > 0:
        if n % 2 == 1:
            result *= x               # multiply when current bit is 1

        x *= x                        # square the base
        n //= 2                       # shift exponent right (divide by 2)

    return result

• 如果 n 的当前最低有效位为 1，则将 result 乘以 x。
• 始终对 x 进行平方并将 n 减半。
• 示例：(x = 2, n = 5)（二进制 101）→ 经过三次迭代后 result = 32。

主交互：浮点基数和整数指数输入

base = float(input("Enter base (x): ").strip())
exponent = int(input("Enter exponent (n): ").strip())

value = fast_power(base, exponent)
print(f"{base}^{exponent} = {value}")

该脚本读取一个浮点数基数和一个整数指数，使用 fast_power 计算幂并打印结果。

总结与思考

• 位检查乘法：n % 2 用来提取最低有效位。
• 始终平方：x *= x 在每次循环中缩小问题规模。
• 负指数处理：通过取倒数的简单转换实现。
• 同样的模式可以扩展到模幂运算（xⁿ mod m），这是 RSA 及其他密码算法的基石。
• 还有递归实现（例如 if n even: (x^{n/2})² else: x·x^{n‑1}），以及用于斐波那契数列的矩阵方法。

后续步骤与资源

• 挑战 #76 的源代码：scripts/binary_exponentiation.py
• 主仓库：80-days-of-challenges
• 每日更新：Twitter/X (@Shahrouzlogs)