11
$\begingroup$

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.

$\endgroup$
2
  • 3
    $\begingroup$ $$\frac{66}{101} < \frac{17}{26} < \frac{19}{29}$$ I don't think the prime factorisation helps, but I think continued fraction expansion will help. $\endgroup$ May 12, 2015 at 15:46
  • $\begingroup$ @DanielFischer Thank you. I corrected the error. $\endgroup$
    – mhp
    May 12, 2015 at 15:54

3 Answers 3

5
$\begingroup$

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
$\endgroup$
2
  • 1
    $\begingroup$ Nice. If anybody wants to check this out further, they should start with Farey sequences. $\endgroup$
    – TonyK
    May 12, 2015 at 17:31
  • $\begingroup$ Another source of further reading is the related Stern-Brocot Tree mediant / binary search; the answer above is identical, except that it initializes the search to [0,1) and not the [0,Infinity) range of the full tree. $\endgroup$ Mar 12, 2017 at 13:42
5
$\begingroup$

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.

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ How do you choose $b$? How do you choose the next value of $b$? Trying all possible values of $b$'s is exponential in complexity. Perhaps I missed something in your answer? $\endgroup$
    – mhp
    May 12, 2015 at 16:21
  • $\begingroup$ How are you measuring the complexity? Exponential in terms of what? $\endgroup$ May 12, 2015 at 16:29
  • $\begingroup$ Exponential in number of operations with respect to number of bits used to represent $U$ and $L$. This is the normal measure of complexity. For example, finding a factor of $n$ by trying $O(\sqrt{n})$ possible divisors is exponential since $n$ has $\log_2 n$ bits. $\endgroup$
    – mhp
    May 12, 2015 at 16:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .