janmr blog

Comparing Rational Numbers Without Overflow

Say you want to know if the inequality

is true ( are all assumed to be positive integers). Of course, one could just multiply both sides with , obtaining the equivalent

and we were done. But if our number representation allowed only numbers up to a certain size, say 32 bit unsigned integers, the multiplication could overflow.

Of course, double-precision could be used to do the multiplication anyway, but this post will present a different method. The method effectively computes the continued fraction representation of each fraction simultaneously, but stops as soon as they differ. It is also the algorithm used for comparisons in the Boost C++ library Rational.

We start by doing the (integer) division on each side of the inequality to obtain the representation

with the quotient and the remainder ().

Now if we have (using properties of the floor function)

Analogously, if we get . In either case, we are done.

When we have transformed the truth value of the first inequality into

with . Now if or the truth value of the inequality is easily determined. For we get

effectively by flipping the fractions and reversing the inequality sign (obtained by multiplying each side of the inequality by ).

We now recursively apply the same approach until the quotients differ or one or both of the remainders is zero.

Let us finish with a small example:

so yes, .