How to compare rational numbers?

Question

This is a homework problem. Given class "Rational" with two integer fields, numerator and denominator, write a function to compare two "Rational" instances. Let r1 = a/b and r2 = c/d. The trivial solution is to compare a*d and b*c. Can we do better?

Answer 1

In the general case, no. If you expect to do a lot of comparisons, a preliminary processing step could take care of normalizing everything (by dividing both numerator and denominator by their gcd, and making the denominator positive), so that equality comparisons would compare a = c and b = d, but computing a*d = b*c is certainly not prohibitive by any means.

Answer 2

If you want the sophisticated solution, convert each of the two fractions to a continued fraction (using a variant of the GCD algorithm). This simple algorithm generates one integer at a time. Compare each pair of integers from the two partial continued fractions. If they are different, exit. Otherwise generate the next pair and continue while there are more. For rationals, the sequence is finite, so it will terminate soon. I believe this is the best method when a,b,c,d are big.

It has been proved that the continued fraction expansions for all square roots irrationals are recurring. So you can use this also to compare those irrationals, even if their binary computer representations would otherwise give you a wrong result (due to truncation). That means that as soon as you detect the repetition in the pattern, you can terminate, proving equality of the two irrationals.