测试十进制是否足够接近有理数

Question

给定一个十进制x，我想测试x是否在分母9999或更小的有理数的10^-12之内。显然，我可以通过查看x，2x，3x等来查看它们是否足够接近整数。但是有没有更高效的算法？

Answer 1

有一种算法叫做continued fraction algorithm，它会给你一定的意义上的“最佳”有理逼近。当分母超过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)