Comparison of two fractions (<and friends)

Question

I have two fractions that I like to compare. They are saved as follows:

 struct fraction { int64_t numerator; int64_t denominator; }; 

I am currently comparing them as follows:

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

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

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

Oh, and by the way: fractions are always kept simplified, and only the numerator can be negative. Perhaps this input restriction makes some algorithm possible ...

Answer 1

If you use GCC, you can use __int128.

Answer 2

Here Boost implements it. Code commented out.

 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 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 continued-fraction components while ( true ) { // The quotients of the current cycle are the continued-fraction // components. Comparing two cf is comparing their sequences, // stopping at the first difference. if ( ts.q != rs.q ) { // Since reciprocation changes the relative order of two variables, // and cf 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 cf 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) cf // 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 cf // components of that variable are infinity, while the other variable // has a finite next cf component. So that other variable has the // lesser value (modulo the reversal flag!). return ( ts.r != zero ) != static_cast<bool>( reverse ); } } 

Answer 3

I did not understand the code in Kos's answer, so this might just duplicate it.

As other people have noted, there are a few simple special cases, for example. b/c > -e/f and -b/c > -e/f if e/f > b/c . Thus, we leave the case of positive fractions.

Convert them to mixed numbers i.e. ab/c and de/f . The trivial case has a != d , so we assume a == d . Then we want to compare b/c with e/f with b <c, e <e. Good b/c > e/f if f/e > c/b . They are more than one, so you can repeat the mixed number test until all the numbers are different.

Answer 4

The case intrigued me, so here is the implementation of Neil's answer, possibly with errors :)

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

Answer 5

Good, so only your numerators are signed.

Special Occasions:

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

Otherwise:

Both of 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, the result of the comparison must be negative.

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