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

我正在寻找一种算法（最好是在go或c中），在可能的分母（dmin，dmax，1注意：bruteforce方法不够有效，因此我正在寻找更聪明/更有效的解决方案。
示例：对于dmin=1和dmax=10，最接近的公共分数是22/7，与pi的距离约为0.001
第一个想法：看看FARY序列，我们可以找到所有分母接近DMAX的最接近的近似值。不幸的是，这个结果没有满足dmin的约束。

最佳答案

我没有时间给出完整的答案，但这里有一个部分的答案。这项技术使用了连分数的概念——网上有很多关于连分数的内容。我将忽略您的值dmin，它在下面没有使用。
把continued fraction expansion of pi送到你需要的地方对于dmax

[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

一些软件，如微软Excel，将使用分数numlo/denomlo，但可能有比这更好的近似。现在找到自然数r的值，它使denomhi - r * denomlo刚好低于（或等于）dmax。
然后numlo/denomlo或(denomhi - r * denomlo)/(denomhi - r * denomlo)是您所期望的最接近pi的分数。看看哪个更近。
该算法是有序对数（dmax）算法，由于pi的性质，它通常要低得多。对于dmax通过预先计算和存储收敛值（numhi和denomhi的值），并在dmax以上搜索denomhi的值，可以生成更快的算法这也只需要28个数字，但是对于分子和分母都需要这个。二进制搜索最多需要5步才能找到它——几乎是即时的。另一种可能是使用更多的存储和更少的计算来存储所有中间部分那个仓库会有几百个，至少三百个。如果你不喜欢pi的连续分式展开的存储列表，你可以使用pi的值来计算它，但是使用双精度（在C中）只会得到我给你显示的28个数字。
更多的研究，请查阅连分式和中间分式。