计算大区间斐波那契数列和时出现溢出错误该如何解决

问题复现 #

你最初使用通项公式实现斐波那契区间和计算时遇到两轮溢出问题：

1. 原生math库版本
   仅支持r≤1472的场景，超过即抛出OverflowError: (34, 'Result too large')，原始代码如下：

import math
def fib(n):
    s5 = math.sqrt(5)
    phi = (1 + s5) / 2
    return int(round(pow(phi, n) / s5))

def calculateSum(l, r):
    sum = fib(r + 2) - fib(l + 1)
    res = sum % 1000000007
    return res

l = 5
r =1400
print(calculateSum(l,r))

2. decimal优化版本
   调整后仅支持r≤4550000的场景，超过仍抛出decimal.Overflow错误，优化后代码如下：

import decimal
def fib(n):
    s5 = decimal.Decimal(5).sqrt()
    phi = (1 + s5) / 2
    return int(round(pow(phi, n) / s5))

def calculateSum(l, r):
    sum = fib(r + 2) - fib(l + 1)
    res = sum % 1000000007
    return res

l = 5
r =4500000
print(calculateSum(l,r))

核心问题根源 #

通项公式法依赖浮点数/高精度十进制数的幂运算，斐波那契数值随n指数级增长，会快速突破数据类型的存储上限；且你需要的是对1e9+7取模后的结果，先计算完整大数再取模的方式完全没有必要，既浪费算力又容易触发溢出。

最优解决方案 #

直接使用矩阵快速幂+模运算实现，不需要计算完整的斐波那契大数，全程整数运算无溢出风险，时间复杂度仅为O(logn)，支持n到1e18级别的计算需求：

MOD = 10**9 + 7

def matrix_mult(a, b):
    # 2*2矩阵乘法，全程带模运算避免溢出
    return [
        [(a[0][0]*b[0][0] + a[0][1]*b[1][0]) % MOD,
         (a[0][0]*b[0][1] + a[0][1]*b[1][1]) % MOD],
        [(a[1][0]*b[0][0] + a[1][1]*b[1][0]) % MOD,
         (a[1][0]*b[0][1] + a[1][1]*b[1][1]) % MOD]
    ]

def matrix_pow(mat, power):
    # 矩阵快速幂，对数级降低运算次数
    result = [[1, 0], [0, 1]] # 初始化单位矩阵
    while power > 0:
        if power % 2 == 1:
            result = matrix_mult(result, mat)
        mat = matrix_mult(mat, mat)
        power = power // 2
    return result

def fib_mod(n):
    if n == 0:
        return 0
    mat = [[1, 1], [1, 0]]
    res_mat = matrix_pow(mat, n-1)
    return res_mat[0][0] % MOD

def calculateSum(l, r):
    # 斐波那契区间和公式：sum(l~r) = fib(r+2) - fib(l+1)
    return (fib_mod(r+2) - fib_mod(l+1)) % MOD

# 测试用例，支持任意大的r值
l = 5
r = 10**18
print(calculateSum(l, r))

方案优势 #

• 全程整数运算，无浮点数精度损失，也不会触发任何溢出错误
• 运算效率极高，即使r为1e18，也仅需要60次左右的矩阵运算，毫秒级即可出结果
• 没有数值上限限制，完全适配任意大的计算需求

替代方案（不推荐） #

如果坚持要使用通项公式法，可以手动调高decimal的精度和溢出阈值，但效率会随r增大快速下降：

import decimal
ctx = decimal.getcontext()
ctx.prec = 2000000 # 根据r的大小调整，r每增加1，prec需要至少加1
ctx.Emax = 999999999 # 调高超额上限避免溢出

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