I have been given two rational numbers $\frac{a}{b}$ and $\frac{c}{d}$, and I have been told that there is a unique rational number $\frac{p}{q}$ satisfying $|q| \leq n$ (where $n$ is some known natural number) which lies in the interval $[\frac{a}{b}, \frac{c}{d}]$.

How do I find this $\frac{p}{q}$? The rational numbers in the input are given as ratio of integers. We can assume that operations on integers take constant time.

The best strategy I know is something that takes time proportional to $n$. It tries to find if there is a rational number with denominator $i$ where $i$ ranges from $1$ to $n$. It goes something like this:

  1. Check if there is any integer between $\frac{a}{b}$ and $\frac{c}{d}$. To do this, check first if $\frac{a}{b}$ or $\frac{c}{d}$ is an integer itself. If not, compute $\lfloor > \frac{a}{b} \rfloor $, and check if $\lfloor \frac{a}{b} \rfloor + 1$ is smaller than $\frac{c}{d}$.
  2. Multiply both $\frac{a}{b}$ and $\frac{c}{d}$ with 2. Check if there is an integer between these two numbers using the steps in 1, and renormalize this obtained rational number by dividing with $2$.
  3. Multiply both of them with $3$ ...
  4. ...

What are some other ways of doing this?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.