Algorithms – Approximate Greatest Common Divisor

Question

I try, without success, to create an algorithm that can compute the average greatest common divisor of a series of integers.
For example, I have the following numbers:

  399, 710, 105, 891, 402, 102, 397, ...  

As you can see, the average gcd is approximately
100, but how to compute it ?

more details:

I try to find the carrier signal length of a HF signal. This signal is an alternation of high levels and low levels.
eg. ----__------____------__-- …
I have the duration of each level, but this time is not accurate.
My aim is to find as quick as possible the base time of the signal.
My first idea was to compute the gcd of the first times I get, to find the carrier of the signal. But I cannot use the classical gcd because the values are not very accurate.
With a perfect signal I would have gcd(400, 700, 100, 900, 400, 100, 400) = 100

Answer 1

I made a similar question here, where I propose a partial solution.

How to find the approximate basic frequency or GCD of a list of numbers?

In summary, I came with this

• being $v$ the list $\{v_1, v_2, \ldots, v_n\}$,
• $\operatorname{mean}_{\sin}(v, x)$ $= \frac{1}{n}\sum_{i=1}^n\sin(2\pi v_i/x)$
• $\operatorname{mean}_{\cos}(v, x)$ $= \frac{1}{n}\sum_{i=1}^n\cos(2\pi v_i/x)$
• $\operatorname{gcd}_{appeal}(v, x)$ = $1 - \frac{1}{2}\sqrt{\operatorname{mean}_{\sin}(v, x)^2 + (\operatorname{mean}_{\cos}(v, x) - 1)^2}$

And the goal is to find the $x$ which maximizes the $\operatorname{gcd}_{appeal}$. Using the formulas and code described there, using CoCalc/Sage you can experiment with them and, in the case of your example, find that the optimum GCD is ~100.18867794375123:

testSeq = [399, 710, 105, 891, 402, 102, 397]
gcd = calculateGCDAppeal(x, testSeq)
find_local_maximum(gcd,90,110)
plot(gcd,(x, 10, 200), scale = "semilogx")