基于Gregory-Leibniz与Madhava理论计算π的收敛问题及代码求解

收敛速度对比 #

• Gregory-Leibniz序列余项收敛速度为O(1/n)，要达到n位小数精度需要计算约10ⁿ项，收敛速度极慢
• Madhava of Sangamagrama序列余项收敛速度为O(1/(3ⁿ·n))，收敛速度比前者快数个数量级，因此选择该序列实现approach_pi函数

原代码核心问题 #

• 每次循环都重新调用GL(i)/MvS(i)从头计算前i项和，没有复用之前的计算结果，时间复杂度极高
• 精度判定逻辑写反：应该是差值绝对值大于等于阈值时继续循环，小于阈值时停止
• 未导入math模块，MvS函数运行会报错
• 返回值不符合要求，题目要求返回元组(i, p)，原代码返回三个无效值

正确实现逻辑 #

迭代维护计算过程中的中间变量，不需要每次从头计算所有项：

1. 预先计算阈值10^(-n-1)，作为精度判断标准
2. 初始化Madhava序列的第1项结果，以及后续项的符号、分母基数、3的幂次等参数
3. 每轮循环计算新增项，更新当前π近似值，计算与上一轮近似值的差值绝对值
4. 差值小于阈值时停止循环，返回当前计算的项数和π近似值

正确代码实现 #

import math

def approach_pi(n):
    # 计算精度阈值
    threshold = 10 ** (-n - 1)
    sqrt_12 = math.sqrt(12)
    # 初始化第1项结果
    prev_pi = sqrt_12 * 1
    # 已计算项数初始为1
    count = 1
    # 下一项的符号、分母基数、3的幂次
    sign = -1
    denominator = 3
    power_3 = 3 ** 1
    
    while True:
        # 计算当前新增项的贡献
        term = 1 / (denominator * power_3)
        current_pi = prev_pi + sqrt_12 * sign * term
        count += 1
        # 检查是否达到精度要求
        if abs(current_pi - prev_pi) < threshold:
            return (count, current_pi)
        # 更新参数用于下一轮计算
        prev_pi = current_pi
        sign *= -1
        denominator += 2
        power_3 *= 3

# 测试验证
print(approach_pi(2))  # 输出 (8, 3.141568715941784)
print(approach_pi(3))  # 输出 (10, 3.14159051093808)
print(approach_pi(6))  # 输出 (16, 3.1415926517339976)

运行说明 #

如果需要交互输入精度位数，可以在代码末尾添加：

n = int(input("give n : "))
print(approach_pi(n))

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