“Approximate” greatest common divisor

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. 

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.

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).

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.

Leave a Comment

Hata!: SQLSTATE[HY000] [1045] Access denied for user 'divattrend_liink'@'localhost' (using password: YES)