假设你有一个是浮点数约的共同数量倍数的列表,例如:
Suppose you have a list of floating point numbers that are approximately multiples of a common quantity, for example
2.468,3.700,6.1699
2.468, 3.700, 6.1699
这是大约1.234倍数。你会如何描述这个近似GCD,你会怎么进行计算或估计它?
which are approximately all multiples of 1.234. How would you characterize this "approximate gcd", and how would you proceed to compute or estimate it?
严格把我的回答这个问题。
您可以运行欧几里得的GCD算法,所有小于0.01(或少数您选择的)是一个伪0。您的号码:
You can run Euclid's gcd algorithm with anything smaller then 0.01 (or a small number of your choice) being a pseudo 0. With your numbers:
3.700 = 1 * 2.468 + 1.232,
2.468 = 2 * 1.232 + 0.004.
所以gcd上述前两个数字的伪是1.232。现在,您可以利用这个GCD与您的最后一个数字:
So the pseudo gcd of the first two numbers is 1.232. Now you take the gcd of this with your last number:
6.1699 = 5 * 1.232 + 0.0099.
所以1.232是伪最大公约数,并且mutiples是2,3,5。为了改善这个结果,你可以采取线性回归的数据点:
So 1.232 is the pseudo gcd, and the mutiples are 2,3,5. To improve this result, you may take the linear regression on the data points:
(2,2.468), (3,3.7), (5,6.1699).
斜率改善的伪GCD。
The slope is the improved pseudo gcd.
警告:这第一部分是算法的数值不稳定 - 如果开始时非常脏数据,你有麻烦了。
Caveat: the first part of this is algorithm is numerically unstable - if you start with very dirty data, you are in trouble.
上一篇:查找字典单词字典、单词