Comparing rational numbers

Question

Given $a,b,c,d \in \mathbb N$ and $b,d \notin \{0\}$,

$$ \begin{eqnarray*} \frac a b < \frac c d &\iff& ad < cb \end{eqnarray*} $$

My questions are:

Given $a,b,c,d$

1. Assuming we can decide $x < y \in \mathbb Z$ in $\mathcal{O}(|x| +|y|)$, is there any way of deciding $ad<cb$ without having to preform the multiplications (or divisions), $a\cdot d$ and $c \cdot b$. Or is there some sort of proof that there is no way.
2. Is there a faster method to compare rational numbers than multiplying out the denominators.

Answer 1

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 < b \wedge c \ge d \Longrightarrow \frac a b < \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 > d) \wedge (a \le c) \Rightarrow \left[\frac a b < \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<c \wedge b < d$, because otherwise we can either solve it with the rules above, or reverse the question to $\frac c d \overset ? < \frac a b$, and we end up with this condition anyhow.

Rules: $$ \left. \\ \frac {(b-a)} b < \frac {(d-c)} d \iff \left[\frac a b < \frac c d\right] \right|_{a<c,b<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 < \frac {c-a} {d-b} \iff \left[\frac a b < \frac c d\right] \right|_{a<c,b<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} < \frac {c} {d} \iff \left[\frac a b < \frac c d\right] \right|_{a<c,b<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 < \frac {ap+q} {bp'+q'} \iff \frac a b < \frac {q} {q'} \right|_{a>q,b>q'} $$

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

$$ \left. \frac a b < \frac {c} {d} \right|_{a>c,b>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 ? < bc$, then you can easily determine $ad \overset ? = bc$, by testing using the algorithm twice, $ad \overset ? < bc$, $bc \overset ? < 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 ? < 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 ? < 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 ? < 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

Answer 2

Here's a very partial attempt at disproof. Suppose that we can make use only of a (constant number of ) additions and subtractions in our decider, as well as a constant number of ${mod}$ w.r.t predefined numbers. In other words, we can do a constant number of $mod\ 2$, $mod\ 3$, etc. in our decider. Then the only quantities we can compute are of the form $q = k_1 a +k_2 b+k_3 c + k_4 d = \sum k_ia$ where the $k$'s are predefined constants. Note that $q$ can be computed in time $O(\sum|a|)$.

Edited This decider purports to determine a bit $B:B=1$ iff $ad>bc$. Consider taking $a,b,c,d$ as points in $\mathbb{R}^4$. The bit $B$ is decided by its position wrt the surface $ad = bc$ which is a hyperboloid in 4 dimensions. If we have a point $(a,b,c,d)$ in the input space, the decider above can compute points within a bounded distance of this input point, i.e. those points $q: |q-a| = k_1,$ etc. This defines a cuboid in 4 d space.

(How to make this more precise?) The distance from the cuboid to the surface is in general unbounded, and hence the surface can't be computed by the decider

Answer 3

Good question. Would you accept level of confidence?

Perhaps do approximate division. I.e.

To compute the bounding approximate quotients of a/b, right shift a by ceil(log_2(b)) and also by floor(log_2(b)). Then we know the accurate quotient is between these two values.

Then, depending on the relative sizes of the four integers, one may be able to rule out certain cases, and get 100% confidence.

One may repeat the procedure for radix other than 2, and by a succession of such operations increase the level of confidence, until a change of sign / tie-break is somehow observed?

That's my first-draft sketch of a method.

Answer 4

is there any way of deciding ad < cb without having to preform the [expensive] multiplications

Sure.

Idea: Compare the decimal expansion bit by bit.

The only nasty bit is that we have to exclude equality first because otherwise we may not terminate.
It is useful to first compare the integer parts because that is easy.

Consider this:

def less( (a,b), (c,d) ) = {
  // Compare integer parts first
  intA = a div b
  intC = c div d

  if intA < intB
    return True
  else if intA > intB
    return False
  else // intA == intB
    // Normalize to a number in [0,1]
    a = a mod b
    c = c mod d

    // Check for equality by reducing both
    // fractions to lowest terms
    (a,b) = lowestTerms(a,b)
    (c,d) = lowestTerms(c,d)

    if a == c and b == d
      return False
    else
      do
        // Compute next digits in decimal fraction 
        a = 10 * a
        c = 10 * c

        intA = a div b
        intC = c div d

        // Remove integer part again
        a = a mod b
        c = c mod d
      while intA == intC

      return intA < intC
    end
  end
}

Note that the do-while loop has to terminate since the numbers are unequal. We do not know how long it runs, though; if the numbers are very close, it could be a while.

Clearly, there are no expensive multiplications; the only ones we need is to multiply the nominators by $10$. In particular, we have avoided computing $ad$ and $cb$ explicitly.

Is this fast? Probably not. There are lots of integer divisons, modulos and gdcs to compute, and we have a loop whose number of iterations is inversly proportional to the distance between the numbers we compare.

---

The helper method:

def lowestTerms(a,b) = {
  d = gcd(a,b)
  if d == 1
    return (a,b)
  else
    return lowestTerms(a div d, b div d)
  end
}