1

给定一个小数 x，我想测试 x 是否在分母 9999 或更小的有理数的 10^-12 以内。显然，我可以通过查看 x、2x、3x 等，并查看其中任何一个是否足够接近整数来做到这一点。但是有没有更有效的算法？

4

3 回答 3

5

有一种称为连分数算法的算法，可以在某种定义的意义上为您提供“最佳”有理近似值。你可以在你的分母超过 9999 的时候停下来，然后回到之前的收敛值，比较一下是否足够接近。当然，如果小数是一个足够小的有理数，算法将提前终止。

于 2010-10-14T00:59:54.693 回答
2

所以，有几件事：

我假设“十进制x”指的是一些浮点表示x。也就是说，您打算以某种实际上不能完美表示 .1 或 1/3 等的格式来实现它。如果您是手动执行此操作或其他有自己的方式来表示小数的东西，这将不会t 申请。

其次，您是否受制于那些特定的分母和公差？我问是因为如果您对 2 的幂没问题（例如，分母高达 8192，容差为 2^-35），您可以轻松利用 IEEE-754 样式浮点都是有理数的事实。使用指数来确定尾数中的哪个数字对应于 2^-13，然后确保尾数的下 22 位为 0（如果精度不够高，无法包含超过该点的 22，则最多为 22）。如果是这样，你就明白了。

现在，如果您不愿意更改您的算法以使用基数 2，您至少可以使用它来缩小范围并进行一些消除。

于 2010-10-14T01:08:19.050 回答
1

我看到你已经接受了一个答案，但我还是要插话。

蛮力方法不需要检查每个分母。如果你逆向工作，你不仅可以消除刚刚检查的数字，还可以消除它的每一个因素。例如，一旦您检查了 9999，您就不需要检查 3333、1111、909、303、101、99、33、11、9、3 或 1；如果数字可以表示为其中一个的分数，它也可以表示为 9999 的分数。事实证明，5000 以下的每个数字都是至少一个数字 5000 到 9999 的因数，所以你已经削减了您的搜索空间减半。

编辑：我发现这个问题很有趣，可以用 Python 编写解决方案。

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def simplify(fraction_tuple):
    divisor = gcd(fraction_tuple[0], fraction_tuple[1])
    return fraction_tuple[0] / divisor, fraction_tuple[1] / divisor

def closest_fraction(value, max_denominator=9999, tolerance=1e-12, enforce_tolerance=False):
    best_error, best_result = abs(value), (0,1)
    for denominator in range(max_denominator/2+1, max_denominator+1):
        numerator = round(value * denominator)
        error = abs(value - (numerator / denominator))
        if error < best_error:
            best_error = error
            best_result = int(numerator), denominator
            if error <= tolerance:
                break
    if enforce_tolerance and best_error > tolerance:
        return None
    return simplify(best_result)
于 2010-10-14T08:47:04.427 回答