Search code examples
c64-bitfractions

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...

Solution

  • If you are using GCC, you can use __int128.