algorithm - 为给定的分母范围找到最接近的 Pi 近似值

Question

我正在寻找一种算法(最好是在 Go 或 C 中)以在可能的分母(dmin,dmax with 1 <= dmin <= dmax <= 1e15)的包含范围内找到最接近 Pi 的公共(public)分数 n/d ).如果有多个公分数到 Pi 的距离相同，我想找到分母最小的分数。

注意:暴力破解方法不够有效，因此我正在寻找更智能/更有效的解决方案。

示例:对于 dmin=1 和 dmax=10，最接近的公分数是 22/7，与 Pi 的距离约为 0.001

第一个想法:查看 faey 序列，我们可以找到所有分母最接近 dmax 的近似值。不幸的是，该结果不满足 dmin 的约束。

Answer 1

我没有时间给出完整的答案，但这里是部分答案。这种技术使用连分数的概念——网上有很多关于它们的内容。我会忽略你的值 dmin，下面没有使用它。

获取continued fraction expansion of pi到你需要的许多地方。对于 dmax <= 1e15 的界限，您只需要前 28 个数字，即

[3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13]

使用短循环找到分母刚好低于和高于 dmax 的 pi 的收敛点。在 Python 中是

pi_cont_frac = [3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 
                3, 1, 14, 2, 1, 1, 2, 2, 2, 2,
                1, 84, 2, 1, 1, 15, 3, 13]
denomlo, denomhi = 1, 0
numlo, numhi = 0, 1
for q in pi_cont_frac:
    denomlo, denomhi = denomhi, q * denomhi + denomlo
    numlo, numhi = numhi, q * numhi + numlo
    if denomhi > dmax:
        break

有些软件，例如 Microsoft Excel，会使用分数 numlo/denomlo，但可能有比这更好的近似值。现在找到使 denomhi - r * denomlo 刚好低于(或等于)dmax 的自然数 r 的值。

那么 numlo/denomlo 或 (denomhi - r * denomlo)/(denomhi - r * denomlo) 就是你想要的最接近圆周率的分数。只需检查哪个更近即可。

此算法的阶数为 log(dmax)，并且由于 pi 的属性，它通常要低得多。对于 dmax <= 1e15，它需要 28 个循环，但需要更多的清理语句。

您可以通过预先计算和存储收敛值(numhi 和 denomhi 的值)并搜索刚好高于 dmax 的 denomhi 值来创建更快的算法。这也只需要 28 个数字，但分子和分母都需要这个。二进制搜索最多需要 5 步才能找到它——几乎是瞬时的。使用更多存储和更少计算的另一种可能性是存储所有中间分数。那个存储量将达到数百个，至少三百个。如果您不喜欢 pi 的连续分数扩展的存储列表，您可以使用 pi 的值来即时计算它，但是使用 double (在 C 中)只会让您得到我向您展示的 28 个数字.

要进行更多研究，请查找连分数和中间分数。