问“近似”最大公因子

EN

您可以运行欧几里得的gcd算法，只要小于0.01 (或您选择的少量)都是伪0。用你的数字：

3.700 = 1 * 2.468 + 1.232,
2.468 = 2 * 1.232 + 0.004. 

所以前两个数字的伪gcd是1.232。现在，用最后一个数字来表示gcd：

6.1699 = 5 * 1.232 + 0.0099.

因此，1.232是伪gcd，乘数为2,3,5。要改进这一结果，可以对数据点进行线性回归：

(2,2.468), (3,3.7), (5,6.1699).

坡度为改进的伪gcd。

注意:算法的第一部分是数值不稳定的--如果你从非常脏的数据开始，你就有麻烦了。

将您的测量值表示为最低值的倍数。这样，你的列表就变成了1.00000，1.49919，2.49996。这些值的分数部分将非常接近1/N，因为N的某些值取决于你的最低值与基频的接近程度。我建议循环增加氮，直到你找到一个足够精细的匹配。在这种情况下，对于N=1 (也就是说，假设X=2.468是您的基本频率)，您会发现标准偏差为0.3333 (这三个值中有两个是X*1的.5 )，这是不可接受的高得令人无法接受的。对于N=2 (即假设2.468/2是您的基本频率)，您将发现几乎为零的标准差(所有三个值都在X/2倍数的.001内)，因此2.468/2是您的近似GCD。

我的计划的主要缺陷是，当最低的测量是最精确的时，效果最好，但情况可能并非如此。这可以通过多次执行整个操作来缓解，每次丢弃测量列表上的最低值，然后使用每次传递的结果列表来确定更精确的结果。另一种细化结果的方法是调整GCD，以最小化GCD的整数倍数与实测值之间的标准差。

这让我想起了寻找实数的有理数近似的问题。标准技术是连续分式展开：

def rationalizations(x):
    assert 0 <= x
    ix = int(x)
    yield ix, 1
    if x == ix: return
    for numer, denom in rationalizations(1.0/(x-ix)):
        yield denom + ix * numer, numer

我们可以直接应用于乔纳森·莱弗勒和斯帕尔的方法：

>>> a, b, c = 2.468, 3.700, 6.1699
>>> b/a, c/a
(1.4991896272285252, 2.4999594813614263)
>>> list(itertools.islice(rationalizations(b/a), 3))
[(1, 1), (3, 2), (925, 617)]
>>> list(itertools.islice(rationalizations(c/a), 3))
[(2, 1), (5, 2), (30847, 12339)]

从每个序列中取出第一个足够好的近似值。(3/2和5/2在此)或者不是直接比较3.0/2.0和1.499189.，您可以注意到925/617使用的整数比3/2大得多，这使3/2成为一个很好的停止位置。

你把哪一个数字除以并不重要。(例如，使用a/b和c/b可以得到2/3和5/3。)一旦有了整数比率，就可以使用shsmurfy的线性回归来细化基础的隐含估计。每个人都赢了！