我有两个我喜欢比较的分数。它们的存储方式如下：
struct fraction {
int64_t numerator;
int64_t denominator;
};
目前，我这样比较它们：
bool fraction_le(struct fraction a, struct fraction b)
{
return a.numerator * b.denominator < b.numerator * a.denominator;
}
这很好用，除了(64 bit value) * (64 bit value) = (128 bit value)，这意味着它会溢出离零太远的分子和分母。
即使对于荒谬的分数，我如何才能使比较始终有效？
哦，顺便说一句：分数总是以简化形式存储的，只有分子可以是负数。也许输入约束使某些算法成为可能......
以下是Boost的实现方式。代码注释很好。
template <typename IntType>
bool rational<IntType>::operator< (const rational<IntType>& r) const
{
// Avoid repeated construction
int_type const zero( 0 );
// This should really be a class-wide invariant. The reason for these
// checks is that for 2's complement systems, INT_MIN has no corresponding
// positive, so negating it during normalization keeps it INT_MIN, which
// is bad for later calculations that assume a positive denominator.
BOOST_ASSERT( this->den > zero );
BOOST_ASSERT( r.den > zero );
// Determine relative order by expanding each value to its simple continued
// fraction representation using the Euclidian GCD algorithm.
struct { int_type n, d, q, r; } ts = { this->num, this->den, this->num /
this->den, this->num % this->den }, rs = { r.num, r.den, r.num / r.den,
r.num % r.den };
unsigned reverse = 0u;
// Normalize negative moduli by repeatedly adding the (positive) denominator
// and decrementing the quotient. Later cycles should have all positive
// values, so this only has to be done for the first cycle. (The rules of
// C++ require a nonnegative quotient & remainder for a nonnegative dividend
// & positive divisor.)
while ( ts.r < zero ) { ts.r += ts.d; --ts.q; }
while ( rs.r < zero ) { rs.r += rs.d; --rs.q; }
// Loop through and compare each variable's continued-fraction components
while ( true )
{
// The quotients of the current cycle are the continued-fraction
// components. Comparing two c.f. is comparing their sequences,
// stopping at the first difference.
if ( ts.q != rs.q )
{
// Since reciprocation changes the relative order of two variables,
// and c.f. use reciprocals, the less/greater-than test reverses
// after each index. (Start w/ non-reversed @ whole-number place.)
return reverse ? ts.q > rs.q : ts.q < rs.q;
}
// Prepare the next cycle
reverse ^= 1u;
if ( (ts.r == zero) || (rs.r == zero) )
{
// At least one variable's c.f. expansion has ended
break;
}
ts.n = ts.d; ts.d = ts.r;
ts.q = ts.n / ts.d; ts.r = ts.n % ts.d;
rs.n = rs.d; rs.d = rs.r;
rs.q = rs.n / rs.d; rs.r = rs.n % rs.d;
}
// Compare infinity-valued components for otherwise equal sequences
if ( ts.r == rs.r )
{
// Both remainders are zero, so the next (and subsequent) c.f.
// components for both sequences are infinity. Therefore, the sequences
// and their corresponding values are equal.
return false;
}
else
{
// Exactly one of the remainders is zero, so all following c.f.
// components of that variable are infinity, while the other variable
// has a finite next c.f. component. So that other variable has the
// lesser value (modulo the reversal flag!).
return ( ts.r != zero ) != static_cast<bool>( reverse );
}
}
如果您使用的是 GCC，则可以使用 __int128。
我不明白科斯回答中的代码，所以这可能只是重复它。
正如其他人所提到的，有一些简单的特殊情况b/c > -e/f，例如-b/c > -e/fif e/f > b/c。所以我们只剩下正分数的情况。
将这些转换为混合数字，即a b/c和d e/f。微不足道的情况有a != d所以我们假设a == d。然后我们要b/c与e/fb < c, e < f 进行比较。好吧b/c > e/f，如果f/e > c/b。这些都大于一，因此您可以重复混合数字测试，直到整数部分不同。
案例引起了我的兴趣，所以这里是 Neil 答案的一个实现，可能有错误：)
#include <stdint.h>
#include <stdlib.h>
typedef struct {
int64_t num, den;
} frac;
int cmp(frac a, frac b) {
if (a.num < 0) {
if (b.num < 0) {
a.num = -a.num;
b.num = -b.num;
return !cmpUnsigned(a, b);
}
else return 1;
}
else if (0 <= b.num) return cmpUnsigned(a, b);
else return 0;
}
#define swap(a, b) { int64_t c = a; a = b; b = c; }
int cmpUnsigned(frac a, frac b) {
int64_t c = a.num / a.den, d = b.num / b.den;
if (c != d) return c < d;
a.num = a.num % a.den;
swap(a.num, a.den);
b.num = b.num % b.den;
swap(b.num, b.den);
return !cmpUnsigned(a, b);
}
main() {
frac a = { INT64_MAX - 1, INT64_MAX }, b = { INT64_MAX - 3, INT64_MAX };
printf("%i\n", cmp(a, b));
}
好的，所以只有你的分子是签名的。
特别案例：
如果 a.numerator 为负而 b.numerator 为正，则 b 大于 a。如果 b.numerator 为负而 a.numerator 为正，则 a 大于 b。
否则：
您的两个分子具有相同的符号 (+/-)。添加一些逻辑代码或位操作以将其删除，并使用乘法与 uint64_t 进行比较。请记住，如果两个分子都是负数，则比较的结果必须取反。
为什么不直接将它们作为浮点数进行比较呢？
bool fraction_le(struct fraction a, struct fraction b)
{
return (double)a.numerator / a.denominator < (double)b.numerator / b.denominator;
}