algorithm - "Approximate"最大公约数

Question

假设您有一个大约常用数量倍数的 float 列表，例如

2.468、3.700、6.1699

大约是 1.234 的所有倍数。您如何描述这个“近似 gcd”，以及您将如何继续计算或估计它？

与我对 this question 的回答严格相关.

Answer 1

您可以运行 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。

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