Python递归计算伯努利数结果偏差问题求助

问题描述 #

尝试用Python计算第n个伯努利数的分子和分母，但递归实现的结果与正确值存在偏差：

• 调用bernoulli(4)得到(-600479950316067, 18014398509481984)，正确值应为(-1, 30)
• 调用bernoulli(6)得到(214457125112883, 9007199254740992)，正确值为(1, 42)
• 调用bernoulli(8)得到(-1200959900632195, 36028797018963968)，正确值为(-1, 30)

原代码如下：

from fractions import Fraction
from math import factorial

def aux_bernoulli(n):
    if n == 0:
        return 1
    elif n == 1: # convention
        return -0.5
    elif (n-1)%2==0: # B(n)=0 when n is odd
        return 0
    else:
        somme = 0
        for k in range(n):
            somme += (factorial(n)/(factorial(n+1-k)*factorial(k))) * aux_bernoulli(k)
        return -somme

def bernoulli(n):
    ber = aux_bernoulli(n)
    print(ber) # for debugging purposes
    numerator, denominator = Fraction(ber).numerator, Fraction(ber).denominator
    return numerator, denominator

问题原因 #

1. 浮点数精度误差：代码中返回-0.5这类浮点数，递归计算时浮点数的累积误差会导致结果偏离精确分数，后续转Fraction也无法恢复精确值。
2. 递推公式系数错误：伯努利数的标准递推公式为：
   $$B_n = -\frac{1}{\binom{n+1}{n}} \sum_{k=0}^{n-1} \binom{n+1}{k} B_k$$
   原代码中使用的系数是$\binom{n}{k}$（即factorial(n)/(factorial(n+1-k)*factorial(k))），缺少了n+1的因子，导致计算结果比例错误。

修正方案 #

全程使用精确分数运算，避免浮点数；同时修正递推公式的系数：

from fractions import Fraction
from math import factorial

def aux_bernoulli(n):
    if n == 0:
        return Fraction(1, 1)
    elif n == 1:  # 遵循约定
        return Fraction(-1, 2)
    elif n % 2 == 1 and n > 1:  # 奇数n>1时B(n)=0
        return Fraction(0, 1)
    else:
        somme = Fraction(0, 1)
        for k in range(n):
            # 计算组合数C(n+1, k)
            comb = factorial(n+1) // (factorial(k) * factorial(n+1 - k))
            somme += comb * aux_bernoulli(k)
        # 递推公式：B(n) = -somme / C(n+1, n)，而C(n+1,n)=n+1
        return -somme / (n+1)

def bernoulli(n):
    ber = aux_bernoulli(n)
    return ber.numerator, ber.denominator

验证结果 #

• bernoulli(4) 返回 (-1, 30)，符合正确值
• bernoulli(6) 返回 (1, 42)，符合正确值
• bernoulli(8) 返回 (-1, 30)，符合正确值

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