1
$\begingroup$

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?

$\endgroup$

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.