Comparing rational numbers
My current research:

Initial attempt at some general rules

One can try to make some general rules for solving the rational comparison:

Assuming all positive $a,b,c,d$:

$$
a &lt; b \wedge c \ge d
 \Longrightarrow 
\frac a b &lt; \frac c d\\
$$
This basically means, if the left side is less than one, and the right side is at least one, the left side is less than the right side. In the same vein:

$$
a \ge b \wedge c \le d
 \Longrightarrow 
\frac a b \not\lt \frac c d\\
$$

Another rule:

$$
(b &gt; d) \wedge (a \le c)
 \Rightarrow
\left[\frac a b &lt; \frac c d\right]
$$
I think of this rule as logical, since the greater the denominator, the smaller the number, while the greater the numerator, the larger the number. Hence if the left side has a greater denominator and a smaller numerator, the left will be smaller.

From here on in, we will assume that $a&lt;c \wedge b &lt; d$, because otherwise we can either solve it with the rules above, or reverse the question to $\frac c d \overset ? &lt; \frac a b$, and we end up with this condition anyhow.

Rules:
$$
\left.
\\
\frac {(b-a)} b &lt; \frac {(d-c)} d
 \iff
\left[\frac a b &lt; \frac c d\right]
\right|_{a&lt;c,b&lt;d} \\
$$
This rule basically states that you can always subtract the numerators from the denominators, and set the results as the numerators, to obtain an equivalent problem. I'll leave out the proof.

$$
\left.
\\
\frac {a} b &lt; \frac {c-a} {d-b}
 \iff
\left[\frac a b &lt; \frac c d\right]
\right|_{a&lt;c,b&lt;d} \\
$$

This rule allows you to subtract the left numerator and denominator from the right numerator and denominator for an equivalent problem.

And of course there is scaling:

$$
\left.
\\
\frac {ak} {bk} &lt; \frac {c} {d}
 \iff
\left[\frac a b &lt; \frac c d\right]
\right|_{a&lt;c,b&lt;d} \\
$$
You can use scaling to make the subtraction rules above more significant.

Using these rules you can play around with things, apply them repeatedly, in smart combinations, but there are cases where numbers are close, and pathological.

By applying the previous rules, you can reduce all these problems to:
$$
\left.
\frac a b &lt; \frac {ap+q} {bp'+q'}
\iff
\frac a b &lt; \frac {q} {q'}
\right|_{a&gt;q,b&gt;q'}
$$

Sometimes you can solve this directly now, sometimes not. The pathological cases are usually in the form:

$$
\left.
\frac a b &lt; \frac {c} {d}
\right|_{a&gt;c,b&gt;d,c\in \mathcal O(a), d \in \mathcal O(b)}
$$

Then you flip it, and result in the same thing, just with one bit less. Each application of the rules + flip reduces it by a digit/bit. AFAICT, you cannot quickly solve it, unless you apply the rules $\mathcal O(n)$ times (once for each digit/bit) in the pathological case, negating their seeming advantage.

Open problem??

I realized that this problem seems to be harder than some current open problems.

An even weaker problem is to determine:

$$ad \overset ? = bc$$

And yet weaker:

$$ad \overset ? = c$$

This is the open problem of verifying multiplication. It is weaker, because if you had a way to determine $ad \overset ? &lt; bc$, then you can easily determine $ad \overset ? = bc$, by testing using the algorithm twice, $ad \overset ? &lt; bc$, $bc \overset ? &lt; ad$. Iff either is true, you know that $ad \ne bc $.

Now, $ad \overset ? = c$ was an open problem, at least in 1986:


  The complexity of multiplication and division. Let us begin with the very 
  simple equation ax = b. When considered over the integers, testing its solvability and finding a solution x is possible by integer division with remainder zero. For checking a given solution x, integer multiplication will suffice, but it is an interesting open problem whether there are faster methods of verification.
  
  ― ARNOLD SCHÖNHAGE in Equation Solving in Terms of 
  Computational Complexity


Very interestingly, he also mentioned the question of verifying matrix multiplication:


  It is also an interesting question whether
  verification of matrix multiplication, i.e., checking whether AB = G for given C, 
  could possibly be done faster.
  
  ― ARNOLD SCHÖNHAGE in Equation Solving in Terms of 
  Computational Complexity


This has been since solved, and it is indeed possible to verify in $\mathcal O(n^2)$ time with a randomized algorithm (with $n\times n$ being the size of the input matrices, so it is basically linear-time in the size of the input). I wonder if it is possible to reduce integer multiplication to matrix multiplication, especially with their similarities, given Karatsuba integer multiplication's similarities to matrix multiplication algorithms that followed. Then perhaps in some way we can leverage the matrix multiplication verification algorithm for integer multiplication.

Anyway, since this is still, to my knowledge, an open problem, the stronger problem of $ad \overset ? &lt; cd$ is surely open. I am curious if solving the equality verification problem would have any bearing on the comparison inequality verification problem.

A slight variation of our problem would be if the fractions are guaranteed to be reduced to lowest terms; in this case it is easy to tell if $\frac a b \overset ? = \frac c d$. Can this have any bearing on comparison verification for reduced fractions?

An even subtler question, what if we had a way to test $ad \overset ? &lt; c$, would this extend to testing $ad \overset ? = c$? I don't see how you can use this "both ways" like we did for $ad \overset ? &lt; cd$.

Related:


Approximate Recognition of Non-regular Languages by Finite Automata

They do some work on approximate multiplication, and randomized verification, which I do not fully understand.
math.SE: How to Compare two multiplications without multiplying?
Suppose we were allowed to preprocess $c$ as much as we wanted in polynomial time, can we solve $ab=c$ in linear time?
Is there a linear-time nondetermistic integer multiplication algorithm? See http://compgroups.net/comp.theory/nondeterministic-linear-time-multiplication/1129399


  There are well-known algorithms for multiplying n-bit numbers with
  something like O(n log(n) log(log(n))) complexity. And we can't do
  better than O(n) because at least we have to look at the entire
  inputs. My question is: can we actually reach O(n) for a suitable
  class of "nondeterministic" algorithms?
  
  More precisely, is there an algorithm that can accept two n-bit
  binary numbers "a" and "b" and a 2n-bit number "c" and tell you in
  O(n) time whether "a * b = c"? If not, is there some other form of
  certificate C(a,b,c) such that an algorithm can use it to test the
  product in linear time? If not linear time, is the problem of
  testing the product at least asymptotically easier than computing
  it? Any known results along these lines would be welcome.
  
  John.
  
  ―johnh4717