Minimal $ab$ for Rational Number $a/b$ in an Interval 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.
 A: 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.
A: 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:


*

*Start with $(a,b,c,d)=(0,1,1,1)$. 

**[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$.

*If $u<Lv$, let $a\leftarrow u$, $b\leftarrow v$ and go to step 2

*If $u\ge Uv$, let $c\leftarrow u$, $d\leftarrow v$ and go to step 2.

*We have found $M=\frac uv$ for which the product $uv$ is minimal. Terminate

A: 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.  
