浮点数列表的 GCD - 分数的输出不正确

Question

我需要一个函数来获取浮点数列表，并计算该列表的gcd。

例如，给定输入[1/2.0, 1/3.0]我希望输出是1/6.0

然而它不是。它打印5.55111512313e-17，换句话说，零。这是我的代码：

def gcd(L):
    return reduce(fractions.gcd, L)
print gcd([1/2.0, 1/3.0])

这是怎么回事？有什么方法可以解决吗？

Answer 1

你需要使用Fraction对象，因为float是不精确的，这就是Fraction类存在的原因：

>>> reduce(fractions.gcd, [Fraction(1,2), Fraction(1,3)])
Fraction(1, 6)

Answer 2

避免经历浮点麻烦，只需将数字保留为分数即可保持其准确性：

import fractions
def gcd(L):
    return reduce(fractions.gcd, map(fractions.Fraction, L))
print gcd(['1/2', '1/3'])
# 1/6

Answer 3

如果您的

程序必须处理浮点输入，"仅使用分数或小数"无济于事。

我已经在我的用例中使用 numpy 完成了以下操作：

def is_mostly_integer(value, epsilon=0.001):
    """
    Tests whether a float value is close to an integer
    Can be applied to numpy arrays
    """
    return numpy.abs(value - value.round()) < epsilon
def float_gcd(float_array, max_trials=100):
    """
    Find the greatest common denominator of a set of float values.
    Assumes that the set of floats was generated by multiplying integers with a float constant.
    """
    numpy_array = numpy.array(float_array)
    sorted_values = numpy.unique(numpy_array)
    sorted_values.sort()
    differences = numpy.diff(sorted_values)
    first_guess = min(differences)
    divisor = next(div for div in range(1, max_trials) if
         is_mostly_integer(sorted_values/first_guess*div).all())
    gcd = first_guess / divisor
    return gcd
for i in range(10000):
    int_arr = numpy.random.randint(-50, 50, (100,))
    factor = numpy.random.randn(1)
    gcd = float_gcd(int_arr * factor)
    assert(is_mostly_integer(gcd/factor))