Python计算无理数高次幂的compute函数性能优化问题

性能问题根源 #

你当前的实现效率极低主要有两个核心原因：

1. 重复计算开销极大：每次处理n时你重复调用了3次compute(a,b,p,n-1)，所有子问题都被重复计算了3次，时间复杂度达到了O(2^n)，n超过20就会有明显卡顿。
2. 递归栈溢出风险：Python默认递归深度上限约为1000，当n大于这个值时代码会直接抛出栈溢出错误。

优化方案 #

方案1：迭代实现（时间复杂度O(n)） #

先把递归改成迭代，用变量保存上一轮的计算结果，避免重复计算，同时解决栈溢出问题：

def compute(a,b,p,n):
    x, y = a, b
    for _ in range(2, n+1):
        new_x = a * x + b * p * y
        new_y = b * x + a * y
        x, y = new_x, new_y
    return (x, y)

这个版本已经可以处理万级别的n，比原递归快几个数量级。

方案2：快速幂实现（时间复杂度O(log n)，最优方案） #

你要计算的本质是(a + b√p)^n的系数，这类幂运算可以用二分快速幂的思路优化，类似整数快速幂的逻辑：我们把两个(x + y√p)形式的数的乘法规则抽象出来，就可以用二分法把幂运算的时间复杂度降到O(log n)，哪怕n是1e18的规模也能快速算出结果。

实现代码如下：

def compute(a,b,p,n):
    # 定义两个 (x + y√p) 形式数的乘法，返回结果的系数元组
    def multiply(num1, num2):
        x1, y1 = num1
        x2, y2 = num2
        res_x = x1 * x2 + p * y1 * y2
        res_y = x1 * y2 + x2 * y1
        return (res_x, res_y)
    
    # 快速幂初始化：结果初始为1 = 1 + 0√p，基数为a + b√p
    result = (1, 0)
    base = (a, b)
    exponent = n
    while exponent > 0:
        # 若当前二进制位为1，乘到结果里
        if exponent % 2 == 1:
            result = multiply(result, base)
        # 基数平方，指数右移一位
        base = multiply(base, base)
        exponent = exponent // 2
    return result

这个实现完全不依赖外部库，运算效率远高于O(n)的迭代版本，是当前问题的最优解。

内容的提问来源于stack exchange，提问作者Hunter