Minimal $ab$ for Rational Number $a/b$ in an Interval

Question

Given rational numbers $L$ and $U$, $0<L<U<1$, find rational number $M=a/b$ such that $L \le M<U$ and $(a\times b)$ is as small as possible---$a$ and $b$ are integers. For example,

• If $L=66/101$ and $U=19/29$ then $M=17/26$.
• If $L=66/101$ and $U=19/28$ then $M=2/3$.

Right now I'm using a naive search that is exponential in complexity. Is there a better method?

If it is of any help, it can be assumed the prime factorization of numerator and denominator of $U$ and $L$ are known.

Answer 1

As per TonyK's answer, it is only necessary to find the smallest denominator for which a fraction in $[L,U)$ exists. To avoid what he calls "messy" oscillations, we can proceed as follows:

1. Start with $(a,b,c,d)=(0,1,1,1)$.
2. *[Remark: We have $\frac ab<L<U\le \frac cd$, and $ad-bc=-1$, and any fraction between $\frac ab$ and $\frac cd$ has denominator $\ge b+d$]*$\quad$ Let $u\leftarrow a+c$, $v\leftarrow b+d$.
3. If $u<Lv$, let $a\leftarrow u$, $b\leftarrow v$ and go to step 2
4. If $u\ge Uv$, let $c\leftarrow u$, $d\leftarrow v$ and go to step 2.
5. We have found $M=\frac uv$ for which the product $uv$ is minimal. Terminate

Answer 2

Why is your algorithm exponential?

Here's an option: Don't think about the numbers as fractions, but as pairs. Your goal is to find the pair $(a,b)$ such that $L\leq a/b\leq U$ such that $a\times b$ is minimal. In this case, we do NOT reduce fractions.

For a fixed $b$, we can easily find the smallest possible $a$ that satisfies the conditions by computing $a=\lceil bL\rceil$. (You must check: If $bL\in\mathbb{Z}$, then use $a+1$ and also check that $a/b<U$.) This $a$ gives the best possible pair with denominator $b$ (anything larger has a larger $a$-value).

Using the best minimum so far, continue computing until your denominator reaches this value. A weak stopping condition is given by the fraction $\frac{1}{2}(L+U)$ which you know is in the interval.

Answer 3

It is enough to find the smallest possible $b$, and then the smallest possible $a$ given $b$. This is not completely obvious, so I will try to prove it:

Suppose we have positive integers $a,b$ such that

(i) $b$ is the smallest denominator of all fractions in $[L,U)$; and

(ii) $a/b$ is the smallest multiple of $1/b$ in $[L,U)$.

This means that $(a-1)/b < L \le a/b$, and so $a-1<bL\le a$.

Now suppose for the sake of contradiction that we have found positive integers $c,d$ such that $c/d \in [L,U)$ and $cd < ab$. Then $b < d$, by (i), so $bL < dL$. (The case $b=d$ is ruled out, because then we would have $c \ge a$, by (ii), and hence $cd \ge ab$.)

But now we have $a-1 < bL < dL \le c$, because $c/d \ge L$.

Hence $a < c$, which together with $b < d$ gives us $ab < cd$, contradicting our assumption.

And to find the smallest denominator in an interval $[L,U)$, it is enough to compute the continued fractions of $L$ and $U$, and truncate them at the first position where they differ. Your examples:

$66/101 = [0;1,1,1,7,1,3]$
$19/29 = [0;1,1,1,9]$
So the answer is $[0;1,1,1,8] = 17/26$

$66/101 = [0;1,1,1,7,1,3]$
$19/28 = [0;1,2,9]$
So the answer is $[0;1,2] = 2/3$

Actually it's not quite as simple as that, because continued fractions oscillate about their convergent, rather than converging monotonically. But you can google "continued fractions" to get the messy details.