Comparing two fractions (< and friends)

问题:

I have two fractions I like to compare. They are stored like this:

struct fraction {
    int64_t numerator;
    int64_t denominator;
};

Currently, I compare them like this:

bool fraction_le(struct fraction a, struct fraction b)
{
    return a.numerator * b.denominator < b.numerator * a.denominator;
}

That works fine, except that (64 bit value) * (64 bit value) = (128 bit value), which means it will overflow for numerators and denominators that are too far away from zero.

How can I make the comparison always works, even for absurd fractions?

Oh, and by the way: fractions are always stored simplified, and only the numerator can be negative. Maybe that input constraint makes some algorithm possible...

回答1:

If you are using GCC, you can use __int128.

回答2:

Here's how Boost implements it. The code is well-commented.

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 );
    }
}

回答3:

I didn't understand the code in Kos's answer so this might be just duplicating it.

As other people have mentioned there are some easy special cases e.g. b/c > -e/f and -b/c > -e/f if e/f > b/c. So we are left with the case of positive fractions.

Convert these to mixed numbers i.e. a b/c and d e/f. The trivial case has a != d so we assume a == d. We then want to compare b/c with e/f with b < c, e < f. Well b/c > e/f if f/e > c/b. These are both greater than one so you can repeat the mixed number test until the whole number parts differ.

回答4:

Case intrigued me, so here is an implementation of Neil's answer, possibly with bugs :)

#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));    
}

回答5:

Alright, so only your numerators are signed.

Special cases:

If the a.numerator is negative and the b.numerator is positive, then b is greater than a. If the b.numerator is negative and the a.numerator is positive, then a is greater than b.

Otherwise:

Both your numerators have the same sign (+/-). Add some logic-code or bit manipulation to remove it, and use multiplication with uint64_t to compare them. Remember that if both numerators are negative, then the result of the comparison must be negated.

回答6:

Why not just compare them directly as floating point numbers?

bool fraction_le(struct fraction a, struct fraction b)
{
    return (double)a.numerator / a.denominator < (double)b.numerator / b.denominator;
}