janmr blog

Comparing Rational Numbers Without Overflow

Say you want to know if the inequality

n1d1<n2d2\frac{n_1}{d_1} < \frac{n_2}{d_2}

is true (n1,n2,d1,d2n_1, n_2, d_1, d_2 are all assumed to be positive integers). Of course, one could just multiply both sides with d1d2d_1 d_2, obtaining the equivalent

n1d2<n2d1  ,n_1 d_2 < n_2 d_1 \; ,

and we were done. But if our number representation allowed numbers only 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

q1+r1d1<q2+r2d2q_1 + \frac{r_1}{d_1} < q_2 + \frac{r_2}{d_2}

with qk=nk/dk0q_k = \lfloor n_k/d_k \rfloor \geq 0 the quotient and rk=nkqkdkr_k = n_k - q_k d_k the remainder (k=1,2k=1,2).

Now if q1<q2q_1 < q_2 we have (using properties of the floor function)

n1d1<q1+1q2n2d2  .\frac{n_1}{d_1} < q_1 + 1 \leq q_2 \leq \frac{n_2}{d_2} \; .

Analogously, if q1>q2q_1 > q_2 we get n1/d1>n2/d2n_1/d_1 > n_2/d_2. In either case, we are done.

When q1=q2q_1 = q_2 we have transformed the truth value of the first inequality into

r1d1<r2d2\frac{r_1}{d_1} < \frac{r_2}{d_2}

with 0rk<dk0 \leq r_k < d_k. Now if r1=0r_1=0 or r2=0r_2=0 the truth value of the inequality is easily determined. For rk1r_k \geq 1 we get

d1r1>d2r2  ,\frac{d_1}{r_1} > \frac{d_2}{r_2} \; ,

effectively by flipping the fractions and reversing the inequality sign (obtained by multiplying each side of the inequality by d1d2/(r1r2)d_1 d_2 / (r_1 r_2)).

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:

355113<2273+16113<3+1711316>717+116>7+01  ,\begin{aligned} \frac{355}{113} &< \frac{22}{7} \quad \Leftrightarrow \\ 3 + \frac{16}{113} &< 3 + \frac{1}{7} \quad \Leftrightarrow \\ \frac{113}{16} &> \frac{7}{1} \quad \Leftrightarrow \\ 7 + \frac{1}{16} &> 7 + \frac{0}{1} \; , \end{aligned}

so yes, 355/113<22/7355/113 < 22/7.