在给定的分母范围内找到Pi的最接近的近似值

我正在寻找一种算法（最好在Go或C中）以找到Pi的最接近的共同部分n/d，其中包含范围可能的分母（dmin，dmax与1 < = dmin < = dmax < = 1e15）。如果有多个与Pi具有相同距离的普通分数，我想找到分母最小的分数。在给定的分母范围内找到Pi的最接近的近似值

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

示例：对于DMIN = 1和Dmax = 10的最接近的共同部分是22/7与大约0.001

首先想到到裨的距离：综观法里数列，我们可以找到所有分母最接近dmax的近似值。不幸的是，结果不符合dmin的约束条件。

来源

2017-02-26 Frank Smith

'44/14'对'dmin = 13'和'dmax = 15'是一个可以接受的答案吗？ –

或者换句话说：是什么激发了'dmin'约束？如果唯一的原因是要确保近似值“足够好”，那么以另一种方式重新说明问题可能会更容易。例如有一个相当简单的算法，用于在给定的有理区间内找到最简单的理性，如果该约束实际上是近似值和pi相差至多1/dmin（这是一个稍微不同的约束），则可以很容易地应用该算法。 –

我没有时间给出完整答案，但这里是部分答案。这项技术使用连续分数的概念 - 网上有很多关于它们的内容。我会忽略你的价值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)是您希望的pi最接近的分数。只要检查哪一个更接近。

该算法的阶数为log（dmax），由于pi的属性，通常要低得多。对于dmax < = 1e15，它需要28个循环，但需要更多的清理声明。

您可以通过预先计算和存储收敛值（numhi和denomhi的值）并在dmax之上搜索denomhi的值来制作更快的算法。这也只需要28个数字，但分子和分母都需要这个数字。二进制搜索最多需要5个步骤才能找到它 - 实际上是瞬时的。使用更多存储和更少计算的另一种可能性是存储所有中间分数。这个存储将进入数百个，至少有三百个。如果你不喜欢这个存储列表来继续扩展pi的分数，你可以使用pi的值来即时计算，但是使用双精度（C）会让你只能看到我给你看的28个数字。

欲了解更多的研究，查找连续分数和中间分数。

来源

2017-02-26 20:04:53

由于满足最小分母约束条件，所以正确答案不一定在pi的连续分数展开式中。 –

没错，这就是为什么我说我的是“一个部分答案”，而“我会忽略你的价值dmin”。完整的答案需要解决您的问题。 –

在给定的分母范围内找到Pi的最接近的近似值

回答

相关问题