“近似”最大公约数

例如，假设您有一个浮点数的列表，这些浮点数的数量大约是常用数量的倍数

2.468,3.700，6.1699

这几乎都是1.234的整数倍。 你如何描述这个“近似gcd”，你将如何继续计算或估计它？

与我对这个问题的回答严格相关。

---

你可以运行Euclid的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直到找到足够精确的匹配。 在这种情况下，对于N = 1（即假设X = 2.468是您的基本频率），您会发现0.3333的标准偏差（三个值中的两个是0.5 * X * 1），这是不可接受的高。 对于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

我们可以直接应用Jonathan Leffler's和Sparr的方法：

>>> 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的线性回归来优化隐含的基本估计。 每个人都赢了！

链接地址: http://www.djcxy.com/p/60865.html

上一篇: "Approximate" greatest common divisor

下一篇: How do I extract files without folder structure using tar