如何比較有理數？

這是一個家庭作業問題。給定具有兩個整數字段（分子和分母）的「Rational」類，編寫一個函數來比較兩個「Rational」實例。讓r1 = a/b和r2 = c/d。微不足道的解決辦法是比較a*d和b*c。我們可以做得更好嗎？如何比較有理數？

2010-11-26 Michael

「更好」的定義是什麼？它看起來非常適合我。 – 2010-11-26 16:02:18

通常情況下，一個分支的成本大於乘法的成本，所以它不值得試圖從中分離出來。如果用整數表示int32，則提升爲int64來執行乘法;如果你的意思是較大的整數，那麼你需要用通常的機制來管理乘法，此時關於分支的假設可以失效。

2010-11-26 22:18:23

-2（a * d）等於-2（b * c）。 – 2010-11-27 11:23:12

在一般情況下，沒有。如果你期望進行大量的比較，初步的處理步驟可以考慮將所有事情規範化（通過將分子和分母除以他們的gcd，並使分母爲正），以便比較比較將比較a = c和b = d，但是計算a * d = b * c當然不是以任何方式禁止的。

2010-11-26 16:03:18

我不喜歡a*d b*c解決方案，因爲如果某些分子和分母很大，可能會導致不必要的整數溢出。雖然我沒有更好的解決方案。

2010-11-26 16:43:30

如果您使用的是Java，那麼當遇到溢出時，您可以使用java.math.BigInteger類;否則，你可以通過字節數組來實現你自己的。

2010-11-26 17:18:15

如果您需要複雜的解決方案，請將兩個分數中的每個分數轉換爲連續分數（使用GCD算法的變體）。這個簡單的算法一次產生一個整數。比較來自兩個部分連續分數的每對整數。如果它們不同，退出。否則，生成下一對，並在有更多時繼續。對於有理數，序列是有限的，所以它很快就會終止。我相信這是a，b，c，d大的最好方法。

已經證明，所有平方根非理性的連續分數展開是重複發生的。所以你可以用它來比較那些無理數，即使它們的二進制計算機表示會給你一個錯誤的結果（由於截斷）。這意味着只要您檢測到模式中的重複，就可以終止，證明兩個無理數的相等性。

2010-11-26 22:16:29 Liberius

從我的角度來看，在平凡的解決方案是在不正確的情況下允許有負數：

什麼r1=1/3和b=1/(-3)這都應該是一個正確的有理數。當然數學它認爲： 1 /（ - 3）< 1/3

然而，所提出的解決方案的產量1*3 > 1*(-3)這導致不正確的解決方案，1/3 < 1/(-3)。

我剛剛在我的Scala課程中遇到過這個問題:-)我仍然沒有很好的解決方案。

也許，像這樣往往可以幫助尋找到升壓庫：有這樣說的：

的比較，用理性的操作做兩雙倍大小的GCD操作，兩個額外的補充和遞減，並在最壞的情況下進行三次比較。（GCD的操作是雙倍的，因爲他們在零碎完成，臨時商被保留，並進行比較，而直接GCD函數只保留和餘數進行比較。）

到目前爲止，我沒有機會調查該代碼。

乾杯，菲利克斯

同時我看看進入加速代碼和像利比里奧在他的回答說明它上面做同樣的。 https://stackoverflow.com/a/4288890/2682209 所以這絕對是「正確」（但繁瑣）的路要走。

2014-05-12 18:52:23 opt12

回答