Search code examples
cstructcomparisonfractions

Comparing fractions with struct


The function is supposed to compare two fractions that are stored in two structs.

  • If fraction L = fraction R return 0
  • If L > R return 1
  • If R > L return -1

Here is the code I have now:

int compare_fractions(Fraction L, Fraction R)
{
    double z = (L.numer/L.denom) - (R.numer/R.denom);
    // THIS CODE IS INCORRECT - FIX IT!  
    if(z == 0)
        return 0;
    else if(z < 0)
        return -1;
    else if(z
        return 1;
}

However when I run the following tests I receive 0's with the following comparisons:

(1,3) ? (2,3)
(5,6) ? (3,4)
(2,4) ? (1,4)

where (1,3) is fraction L and (2,3) is fraction R


Solution

  • If the numerator and denominator are ints (or another integer type) then the division is integer division, you'll never get the correct fractional part

    Casting it to double can correct most of the problem but you'll face the slow divisions and sometimes errors due to floating-point roundings.

    You should use multiplication instead. It'll be much faster and you don't need a floating-point division which is very slow on some architectures. This way you don't need to worry about floating-point comparisons either

    int compare_fractions(Fraction L, Fraction R)
    {
        int z = L.numer*R.denom - L.denom*R.numer;
        if (z == 0)
            return 0;
        else if (z > 0)
            return 1;
        else
            return -1;
    }
    

    Of course you need to make sure that all the denominators are positive, otherwise you need to normalize it (you can use chux's suggestion below). You also need to account for overflow if you values can be large by doing the math in a wider type like

    long long z = (long long)L.numer*R.denom - L.denom*R.numer
    

    If you can lax the requirements a bit to return negative, 0 or positive values for less than, equal or more than case just like strcmp() then you can remove the checks for z's value altogether and return L.numer*R.denom - L.denom*R.numer directly instead

    If you still need to return -1, 0 and 1 then there are several ways to shorten/optimize it like

    return (z > 0) - (z < 0);
    return (z == 0) ? 0 : (z < 0 ? -1 : 1);
    return (z >> 31) | (!!z);