测试小数是否足够接近有理数

Question

给定一个十进制 x，我想测试 x 是否在分母为 9999 或更小的有理数的 10^-12 范围内。显然，我可以通过查看 x、2x、3x 等来完成此操作，并查看其中是否有任何一个足够接近整数。但有没有更高效的算法呢？

Answer 1

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

Answer 2

所以，有几件事：

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

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

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

Answer 3

我看到你已经接受了答案，但无论如何我还是要插话。

蛮力法不需要检查每个分母。如果你倒退，你不仅可以消除你刚刚检查的数字，还可以消除其中的每个因素。例如，一旦您检查了 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)