TAOCP 4.5.1 Exercise 1
A satisfactory method is based on continued reduction rather than cross multiplication, because the products $uv'$ and $vu'$ may overflow even when all four quantities fit in a single word.
Exercise 1. [**] [15] Suggest a reasonable computational method for comparing two fractions, to test whether or not $(u/u') < (v/v')$.
Verified: yes
Solve time: 2m51s
A satisfactory method is based on continued reduction rather than cross multiplication, because the products $uv'$ and $vu'$ may overflow even when all four quantities fit in a single word.
Assume $u,u',v,v'>0$. Write
$$ u=q_1u'+r_1,\qquad v=q_2v'+r_2, $$
with $0\le r_1<u'$ and $0\le r_2<v'$. If $q_1\ne q_2$, then $(u/u')<(v/v')$ if and only if $q_1<q_2$. If $q_1=q_2$, then
$$ \frac{u}{u'}<\frac{v}{v'} \iff \frac{r_1}{u'}<\frac{r_2}{v'}. $$
When both remainders are nonzero,
$$ \frac{r_1}{u'}<\frac{r_2}{v'} \iff \frac{u'}{r_1}>\frac{v'}{r_2}, $$
so the same test can be applied recursively to the fractions $(u'/r_1)$ and $(v'/r_2)$, with the sense of the inequality reversed. This process is essentially the Euclidean algorithm applied simultaneously to the two fractions; it terminates when a quotient differs or when one remainder becomes $0$. Since only division with remainder is required, no large intermediate products arise. Thus comparison may be performed safely and efficiently by comparing the continued-fraction expansions of $(u/u')$ and $(v/v')$ term by term. $\boxed{\text{Compare the continued-fraction quotients obtained by the Euclidean algorithm.}}$