Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.
share|improve this question
    
Multiplication is perhaps the simplest thing to do. Note that to make the decision, we need to process at least $O(|a|+|b|+|c|+|d|)$ bits. You can artificially do without multiplications : add $a$ to itself $d-1$ times instead of doing $a.d$ directly. But surely this isn't what you are looking for? –  PKG Oct 23 '12 at 19:06
1  
@PKG but multiplication will take more than linear time. I think we want something faster for this question. –  Joe Oct 23 '12 at 19:43
1  
The tricky case is when one interval contains another, e.g. $[a,d] \subset [b,c]$. –  PKG Oct 23 '12 at 21:19
1  
You implicitly assume that $b$ and $d$ have the same sign. Otherwise, the inequality direction changes. –  Ran G. Oct 24 '12 at 2:34
1  
(1) Multiplication is almost linear (search for Fürer's algorithm). (2) A "rational integer", at least in the context of algebraic number theory, actually just means an integer. You want to say "rational" or "rational number". –  Yuval Filmus Oct 24 '12 at 23:38

3 Answers 3

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

share|improve this answer

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.

share|improve this answer
    
If you look at my "current research" answer, I think those rules do something to this effect. You can keep going, many times getting 100% confidence if it hits one of the first rules, and in the worst, you keep repeating the latter rules over and over removing a bit each round, similarly to what you are suggesting, I think. However, my question is about something definitive in $\mathcal O(n)$ (or rather, better than multiplication, $\mathcal O(n \log n)$ would satisfy this question too), or at least a randomized algorithm with some exponentially small probability of failure. –  Realz Slaw Nov 25 '12 at 15:17
    
Also, if one could verify that this is an open problem, and not somehow inherently harder than verifying $ab=c$ (see my "current research" answer, section Open Problem??), or if there is some other interesting existing research or results about this, then that too could be an acceptable answer. –  Realz Slaw Nov 25 '12 at 15:42

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

share|improve this answer
    
Sorry I didn't respond to this. I think this might simply be above my understanding, and I've been busy researching possible answers myself in the meantime. –  Realz Slaw Nov 25 '12 at 17:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.