找到噪声数据近似最大公分母的算法？

Question

我有一组值是某个最大公分母的倍数，我需要找到它。如果它们是精确值，我可以简单地使用例如求 GCD 的欧几里得算法。问题是它们是具有不可忽略的采样误差的测量，而不是精确的值，并且欧几里得的算法不能很好地工作（它大约计算出一个非常小的 GCD，这对我来说并不是真正有用）。虽然它们可以被认为是二维中的点，但 X 值是未知的，所以我不能使用线性回归算法（尽管根据定义，X 值将是整数，所以我不知道这个事实是否有助于解决某些问题）方式）。此外，真正的 GCD 不一定是整数。

我怎样才能计算出近似的 GCD？

Answer 1

所提出的问题有些不太明确。因为，显然，当你允许近似实数时，就有无限多个可能的 GCD。

让我们将测量视为一个范围

(start, stop)

。这相当于说我们测量

(start + stop) / 2)

时出现错误

(stop - start)/2

，但事实证明很容易使用。这是一个 Python 示例。

def divisor_ranges (measurement):
    start, stop = measurement
    i = 1
    while stop / (i+1) < start / i:
        yield (start / i, stop / i)
        i += 1
    yield (0, stop / i)

给定一次测量，我们得到一系列范围。我们可以在其中找到除数。我们正在尝试将所有系列相交以进行所有测量。因此，让我们尝试获取与给定范围相交的部分。

def divisor_ranges_in_range (measurement, range_measurement):
    start, stop = measurement
    range_start, range_stop = range_measurement
    i = math.ceil(start / range_stop)
    while True:
        if stop / i <= range_start:
            break # Too small
        elif stop / (i+1) < start / i:
            yield (max(range_start, start/i), min(range_stop, stop/i))
            i += 1
        else:
            yield (range_start, min(range_stop, stop/i))
            break # Just issued our final range.

现在我们可以递归地组合这些来找到公约数在哪里。

def common_divisor_ranges (measurements):
    if len(measurements) == 1:
        yield from divisor_ranges(measurements[0])
    elif 1 < len(measurements):
        measurement = measurements[0]
        for range_measurement in common_divisor_ranges(measurements[1:]):
            yield from divisor_ranges_in_range(measurement, range_measurement)

现在我们可以很容易地找到一个合理的答案。

def gcd (measurements):
    for answer in common_divisor_ranges(measurements):
        return (answer[0] + answer[1])/2

作为演示：

print(gcd([(98, 102), (50, 52), (129, 133)]))

很快就会找到

10.1

作为我们的 GCD。对应实际值

10*10.1 = 101, 5*10.1 = 50.5, 13*10.1 = 131.3

.

我怀疑有隐藏的要求。例如，您的测量结果是整数，这表明您可能希望基础值是整数。这将需要额外的逻辑来提出超出可以找到公约数的范围的候选 GCD。