如何修改Memoisation实现，使缓存清空时可直接计算Bernoulli数B₈？

问题描述 #

我尝试计算若干伯努利数，并采用记忆化（Memoisation）技术优化计算。现有代码中，若预先计算0至7的伯努利数并填充缓存，可正常得到n=8的伯努利数；但清空缓存后直接调用bernoulli(8)无法运行成功。请问需要对代码做出哪些修改，才能在缓存清空时直接计算n=8的伯努利数？

原代码 #

from fractions import Fraction
from scipy.special import comb
import numpy as np

# memoisation
bernoulli_cache = {}

def bernoulli(n: float):
    # check input, if it exists, return value
    if n in bernoulli_cache:
        return bernoulli_cache[n]
    
    # when input is 0 or 1
    if n == 0:
        value = Fraction(1)
    else:  
        value = Fraction(1)
        for k in range(n):
            value -= Fraction(comb(n, k)) * Fraction(bernoulli(k), (n - k + 1))
            
    # write to cache
    bernoulli_cache[n] = value
    
    # fraction parts for output
    numerator = value.numerator
    denominator = value.denominator
    
    return numerator, denominator

# test this works- bits in cache aleady
bernoulli_cache = {}
bernoulli(0) # 1     
bernoulli(1) # 1/2    
bernoulli(2) # 1/6     
bernoulli(3) # 0
bernoulli(4) # −1/30
bernoulli(5) # 0
bernoulli(6) # 1/42
bernoulli(7) # 0
bernoulli(8) # -1/30

# this doesn't  - bits not in cache
bernoulli_cache = {}
bernoulli(8) # -1/30

问题分析 #

原代码存在三个核心问题导致直接调用失败：

• 返回值不一致：缓存存在时返回Fraction对象，缓存不存在时返回(分子, 分母)元组，递归调用时会将元组传入Fraction构造函数，引发类型错误。
• 递推公式错误：使用了不正确的伯努利数递推逻辑，导致计算过程中数值偏差。
• 未利用奇数项性质：大于1的奇数伯努利数为0，原代码未做特殊处理，增加了不必要的递归计算。

修改后的代码 #

from fractions import Fraction
from scipy.special import comb

# 记忆化缓存
bernoulli_cache = {}

def bernoulli(n: int):
    # 检查缓存，存在则直接返回Fraction对象
    if n in bernoulli_cache:
        return bernoulli_cache[n]
    
    # 处理特殊情况
    if n == 0:
        value = Fraction(1)
    elif n == 1:
        value = Fraction(1, 2)
    elif n % 2 == 1:
        # 大于1的奇数伯努利数为0
        value = Fraction(0)
    else:
        # 正确的伯努利数递推公式：B_n = -1/(n+1) * sum_{k=0}^{n-1} C(n+1, k) * B_k
        total = Fraction(0)
        for k in range(n):
            total += comb(n+1, k) * bernoulli(k)
        value = -total / (n + 1)
    
    # 写入缓存
    bernoulli_cache[n] = value
    
    # 返回分子和分母
    return value.numerator, value.denominator

# 测试直接计算n=8
bernoulli_cache = {}
print(bernoulli(8))  # 输出 (-1, 30)，对应-1/30

修改说明 #

• 统一返回值逻辑：递归调用全程操作Fraction对象，缓存存储的也是Fraction，避免类型混合错误。仅在最终返回时转换为分子分母元组，满足输出需求。
• 修正递推公式：采用伯努利数的标准递推公式，确保计算逻辑正确。
• 优化奇数项处理：直接返回大于1的奇数的伯努利数为0，减少递归次数，提升计算效率。
• 修正参数类型：将参数类型从float改为int，符合伯努利数下标的整数特性。

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