如何比较有理数?

通常一个分支的成本比乘法的成本还高,所以除了这个之外,想变得聪明是不值得的。如果所指的整数是int32,则升级到int64以执行乘法;如果所指的整数较大,则需要使用常用机制管理乘法,此时有关分支的假设可能会失效。

在一般情况下,不是。如果你想做很多比较,一个初步的处理步骤可以把所有的东西都规范化(把分子和分母除以它们的gcd,使分母为正),这样平等比较就会比较a=c和b=d,但是,计算a*d=b*c绝对不是禁止的。

如果需要复杂的解决方案,请将这两个分数中的每一个转换为连续分数(使用GCD算法的变体)。这个简单的算法一次生成一个整数。比较两个部分连分数中的每一对整数。如果它们不同,退出。否则,生成下一对并在有更多对时继续。 对于有理数,序列是有限的,所以它很快就会终止。 我相信这是当a,b,c,d很大的时候最好的方法。

证明了所有非有理平方根的连分式展开式都是递归的。所以你也可以用这个来比较那些非理性的,即使它们的二进制计算机表示会给你一个错误的结果(由于截断)。 这意味着一旦你检测到模式中的重复,你就可以终止,证明两个非理性的相等。

在我看来,如果允许出现负数,那么琐碎的解决方案是不正确的:

那怎么办 r1=1/3 和 b=1/(-3) 两者都应该是正确的有理数。当然,数学上它认为: 1/(-3)<1/3

然而,建议的解决方案产生了 1*3 > 1*(-3) 从而导致错误的解决方案 1/3 < 1/(-3) .

我刚刚在Scala课程中遇到了这个问题:—)我仍然没有一个好的解决方案。

也许,就像经常查看BOOST库一样,它会说:

compare with rational操作执行两个双大小的GCD操作、两个额外的加法和减法,以及最坏情况下的三个比较。(GCD操作是两倍大小的,因为它们是逐段执行的,中间商被保留和比较,而直接GCD函数只保留和比较剩余的商。)

http://www.boost.org/doc/libs/1_55_0/libs/rational/rational.html

到目前为止,我还没有机会调查那段代码。

干杯, 费利克斯

与此同时,我查看了Boost代码,它的功能与Liberius在上面的回答中描述的一样。 https://stackoverflow.com/a/4288890/2682209 所以这绝对是“正确的”(但很麻烦)的方法。

我不喜欢 a*d b*c 解决方案,因为如果某些分子和分母较大,则可能导致不必要的整数溢出。尽管我没有更好的解决办法。

如果您使用Java,那么可以使用 java.math.BigInteger 当遇到溢出时初始化;否则,可以通过字节数组实现自己的。