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$ – Daniel Fischer May 12 '15 at 15:46
  • $\begingroup$ @DanielFischer Thank you. I corrected the error. $\endgroup$ – mhp May 12 '15 at 15:54
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 '15 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$ – Eli Collins Mar 12 '17 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 '15 at 16:21
  • $\begingroup$ How are you measuring the complexity? Exponential in terms of what? $\endgroup$ – Michael Burr May 12 '15 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 '15 at 16:39

Your Answer

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

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