使用Stern-Brocot树计算π连分数卡在245850922/78256779问题求助

问题原因 #

1. 触发停止的核心原因是浮点数比较的精度截断，而非效率问题。你卡住的245850922/78256779是π的第10个有理收敛项，和π的误差约为1.5e-16，当这个差值小于当前mpmath浮点数的最小可分辨单位（ULP）时，mp.fdiv(m,n) == mp.pi的判断就会为真，直接触发break退出。
2. 调高mp.dps不生效的原因是mpmath的常量缓存机制：mp.pi的精度在你第一次访问时就会被缓存，如果在修改mp.dps之前你已经访问过mp.pi，之后再调整精度也不会更新mp.pi的实际存储精度，所以始终会卡在对应旧精度的收敛项位置。
3. 当前代码存在额外性能隐患：eval_stern_seq每次都从头遍历整个序列计算分数，当序列长度超过万级之后会严重变慢，但这不是当前停止的原因。

解决方案 #

1. 替换浮点数比较逻辑，避免除法精度损失 #

利用不等号性质将除法比较转换为乘法比较，大幅降低精度损失：

# 原比较逻辑
if mp.fdiv(stern_frac[0],stern_frac[1]) > mp.pi:
    seq+='L'
elif mp.fdiv(stern_frac[0],stern_frac[1]) < mp.pi:
    seq+='R'
else:
    break

# 替换为以下逻辑
m, n = stern_frac
pi_mult_n = mp.pi * n
if m > pi_mult_n:
    seq += 'L'
elif m < pi_mult_n:
    seq += 'R'
else:
    break

2. 确保π的精度足够，避免缓存问题 #

每次调整mp.dps之后，手动刷新mp.pi的精度：

# 示例：设置2000位十进制精度
mp.dps = 2000
# 清除旧的π缓存，强制重新生成高精度值
mp.mp._pi = None
_ = mp.pi

如果需要生成N位精度的连分数，需要把mp.dps设置为至少N+10位，预留足够的精度余量，避免比较时提前触发相等判断。

3. 优化迭代逻辑，解决后续性能问题 #

不用每次从头计算分数，直接维护Stern-Brocot树的区间边界变量，每步迭代仅需O(1)运算，性能提升数个量级：

import mpmath as mp
mp.dps = 2000
mp.mp._pi = None
_ = mp.pi

# 初始化Stern-Brocot区间边界：左边界0/1，右边界1/0
a, b = 0, 1
c, d = 1, 0
seq = ''

while True:
    m, n = a + c, b + d
    print(f"\n\ncurrent fraction:    {m}/{n}")
    print("current value:       " + mp.nstr(mp.fdiv(m,n),n=mp.dps))
    print("pi (reference):      " + mp.nstr(mp.pi,n=mp.dps))

    pi_mult_n = mp.pi * n
    if m > pi_mult_n:
        c, d = m, n
        seq += 'L'
    elif m < pi_mult_n:
        a, b = m, n
        seq += 'R'
    else:
        break

    input("\n\t(press enter to continue generation...)")

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