如何优化π分数估算器？大取值上限下计算耗时过长求方案

我见过22/7、355/113这类圆周率（π）的分数近似值，因此编写了一段Python程序，通过指定取值范围上限（specificity），遍历该范围内的数值寻找最接近π的分数。但当取值上限超过1,000,000时，程序需要数小时才能完成。以下是我的代码，请问有哪些可行的优化方法？

原代码 #

from math import pi, inf, ceil
from time import time, gmtime, strftime

print("\033c", end="")

specificity = int(input("Specificity? "))

fraction = [0, 0]

min_diff = inf

progress_print_interval = 0.05

start_time = time()

last_progress_print = time()

print()
print()

for i in range(specificity):
    for j in range(ceil(i / 3.1)):
        if not i or not j:
            continue
        if abs(i / j - pi) < min_diff:
            min_diff = abs(i / j - pi)
            fraction = [i, j]
        if (time() > last_progress_print + progress_print_interval):
            last_progress_print = time()

            total = i * (i / 3.1) + j / (i / 3.1)

            percent = total / (specificity * (specificity / 3.1))

            print("\033[F", end="")
            print("\033[F", end="")
            print(f"{(percent * 100):2f}%")
            print("Estimated time remaining:", strftime(f'%H:%M:%S', gmtime((time() - start_time) / percent - (time() - start_time))))

print("\033c", end="")
print("Done!")
print(f"{fraction[0]}/{fraction[1]}: {fraction[0] / fraction[1]}")

# best estimation so far: 833719/265381: 3.141592653581078

可行优化方法 #

1. 用连分数展开替代暴力遍历 #

π的最优分数近似（比如22/7、355/113）都是π的连分数收敛项，这是数学上已知的最精准且高效的方法，不需要遍历所有数。连分数展开可以直接生成一系列逼近π的分数，每一项的精度都远高于暴力遍历找到的非收敛项，而且时间复杂度是O(k)（k为收敛项数量），就算要生成分母百万级的收敛项，也只需要几十次迭代。

示例实现：

from math import pi

def pi_continuous_fractions(max_denominator):
    a0 = int(pi)
    m = 0
    d = 1
    a = a0
    h_prev_prev = 1
    h_prev = a0
    k_prev_prev = 0
    k_prev = 1
    best_frac = [h_prev, k_prev]
    min_diff = abs(h_prev / k_prev - pi)
    
    while k_prev <= max_denominator:
        m = d * a - m
        d = (pi - m) / d
        a = int((a0 + m) / d)
        
        h_current = a * h_prev + h_prev_prev
        k_current = a * k_prev + k_prev_prev
        
        # 更新最优分数
        current_diff = abs(h_current / k_current - pi)
        if current_diff < min_diff and k_current <= max_denominator:
            min_diff = current_diff
            best_frac = [h_current, k_current]
        
        h_prev_prev, h_prev = h_prev, h_current
        k_prev_prev, k_prev = k_prev, k_current
    
    return best_frac, min_diff

specificity = int(input("Specificity? "))
frac, diff = pi_continuous_fractions(specificity)
print(f"{frac[0]}/{frac[1]}: {frac[0]/frac[1]}，与π的差值：{diff}")

2. 优化暴力遍历的循环范围 #

如果坚持用暴力遍历，先缩小循环的有效范围：

• 对于分母j，分子i应该在pi*j - 1到pi*j + 1之间，而不是遍历所有i到specificity。这样可以把双重循环改成单循环遍历j，然后计算对应的i，大幅减少循环次数。
• 原代码中range(ceil(i/3.1))的范围不够精准，换成基于π的范围计算，能进一步缩小j的遍历区间。

修改后的暴力遍历核心逻辑：

for j in range(1, specificity+1):
    # 计算i的近似范围
    i_low = int(pi * j - 1)
    i_high = int(pi * j + 1)
    # 确保i不超过上限且大于0
    i_low = max(i_low, 1)
    i_high = min(i_high, specificity)
    for i in range(i_low, i_high+1):
        current_diff = abs(i/j - pi)
        if current_diff < min_diff:
            min_diff = current_diff
            fraction = [i, j]

3. 移除冗余的进度计算逻辑 #

原代码中进度计算部分有大量重复浮点运算，且频繁的终端光标操作会拖慢速度。可以把进度计算间隔调大（比如1秒），或者提前计算总循环次数，用已完成的j数直接计算进度，避免复杂的浮点运算。

4. 使用整数运算减少误差与耗时 #

把abs(i/j - pi)换成整数运算abs(i - pi*j)，既可以减少浮点误差，又能提升计算速度（整数运算比浮点运算更快）。

5. 只处理最简分数 #

利用math.gcd（Python3.5+）判断i和j是否互质，只处理最简形式的分数，避免重复计算等价分数（比如44/14和22/7），减少无效运算。

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