給定一個十進制x,我想測試x是否在分母9999或更小的有理數的10^-12之內。顯然,我可以通過查看x,2x,3x等來查看它們是否足夠接近整數。但是有沒有更高效的算法?測試十進制是否足夠接近有理數
1
A
回答
5
有一種算法叫做continued fraction algorithm,它會給你一定的意義上的「最佳」有理逼近。當分母超過9999時,可以停止,然後返回到前一個收斂,並比較它是否足夠接近。當然,如果小數點是一個足夠小的有理數,算法會提前終止。
2
所以,幾件事情:
我認爲用「十進制X」你指的是一些浮點表示X。也就是說,你打算以某種格式來實現這個功能,而這種格式實際上不能完全代表.1或1/3等。如果你是通過手工或其他方式來表達小數的方式,不適用。
其次,您是否與這些具體的分母和容差相關聯?我問,因爲如果你對2的冪是可以的(例如分母高達8192,容忍度爲2^-35),你可以很容易地利用IEEE-754風格浮點都是有理數的事實。使用指數來確定尾數中的哪個數字對應於2^-13,然後確保尾數的後22位數字爲0(或者如果精度不夠高,以至於超過該點,則包括22),則最多爲22。如果是這樣,你就明白了。
現在,如果你不想改變你的算法來使用基2,你至少可以用它來縮小它,並做一些消除。
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)
相關問題
- 1. 單元測試:是否足夠好?
- 2. 末端2端測試是否足夠?
- 3. Allign元素足夠接近
- 4. 單元測試和驗收測試是否足夠?
- 5. 足夠的硒測試?
- 6. RSPEC能否處理90%通過的測試就足夠了?
- 7. TensorFlow推理(服務),CPU是否足夠?
- 8. 測試的十六進制數值
- 9. 收聽事件「足夠接近」元素
- 10. .htaccess目錄限制是否足夠?
- 11. Entity Framwork是否將十進制值舍入爲最接近的整數?
- 12. 選擇一個十六進制附近的十六進制數
- 13. Gmail是否足夠安全?
- 14. LayoutAwarePage的MVVM是否足夠?
- 15. java.util.regexp是否足夠高效?
- 16. MinGW是否足夠穩定
- 17. shell腳本是否足夠?
- 18. uNhAddIns是否足夠活躍?
- 19. PHP是否足夠動態?
- 20. 這是否足夠安全?
- 21. 確定行-1測試用例中是否有足夠的票據更改
- 22. 十進制小數到最接近的分數
- 23. Hibernate事務回滾需要還是足夠接近?
- 24. 十進制和二進制數處理
- 25. 如何測試Clojure中兩個數字是否接近
- 26. 是否有足夠的併發連接到MySQL服務器?
- 27. 測試平等的足夠方法
- 28. 量角器e2e足夠角度測試
- 29. 只有當物體足夠接近時纔會捕捉物體
- 30. 如何確定十六進制值與白色有多接近?
這對3/7這樣的東西有幫助嗎? – 2010-10-14 02:17:29
你已經指定你的輸入是一個小數(並且我假定了一個有限長度),所以我不確定你的意思究竟是什麼(因爲3/7是一個重複小數,我想你可以運行它到一些數字的位數,然後測試) – Dusty 2010-10-14 02:44:47
他的意思是0.4285714285714的輸入應該返回3/7,因爲它在3/7的10^-12之內。 – 2010-10-14 04:18:44