Approximating a fraction with a given denominator

Question

Let $M$, $N$ be large natural numbers (say ~200 bits). Let $L$ be a smaller number, (say ~100 bits).

I want to approximate the fraction:

$$\frac{M}{N} \sim \frac{k}{L+r}$$

where $r$ is at most $L$. In other words, I want to find good approximations to $M/N$ with denominator larger than $L$ but less than $(1+\delta)L$ where $\delta < 1$ (say $0.5$ for example).

The standard Stern-Brocot binary search tree can give me good approximations, but it gives no guarantee that these approximations have denominator between $L$ and $(1+\delta)L$.

https://www.johndcook.com/blog/2010/10/20/best-rational-approximation/

https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree

https://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations

Any modifications we can make to the search to give us the desired approximations?

Answer 1

Using continued fraction expansion of the number $M/N$ you can find all best approximations of the first or the second kind. Probably you ask about best approximations of the first kind: a rational fraction $a / b$ (for $b>0$) is a best approximation (of the first kind) of a real number $a$ if every other rational fraction with the same or smaller denominator differs from $\alpha$ by a greater amount, in other words, if the inequalities $0<d \leq b$, and $a / b \neq c / d$ imply that $$ \left|\alpha-\frac{c}{d}\right|>\left|\alpha-\frac{a}{b}\right|. $$ (See Khinchin A. Ya., Continued fractions.) It is known that (see Khinchin, Theorem 15) every best approximation of a number a is a convergent or an intermediate fraction of the continued fraction representing that number.

For a given $L$ you can find two consequtive convergents $p_k/q_k$ and $p_{k+1}/q_{k+1}$ such that $q_k\le L< q_{k+1}$. After that you can find all intermediate fraction between $p_k/q_k$ and $p_{k+1}/q_{k+1}$ and choose an appropriate fraction with a denominator close to $L$. It can be a situation when there are no such denominators in the interval $[L,2L].$ In this case you can take the smallest denominator which is greater than $L$.

Answer 2

This can be modelled as two variable integer linear programming, which can be solved in polynomial time. You want to minimize $M r - N k$, subject to $L \leq r \leq (1+\delta)L$ and $M r - N k \geq 0$. Additionally, solve the equivalent for a smaller value — maximize $M r - N k$ subject to it being less than 0.