測試十進制是否足夠接近有理數

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)