I was looking for a way to approximate a decimal number with a fraction, whose denominator is less or equal to $d$. Basically, having a decimal $X$, I want to find two fractions such that $$\frac{a_1}{b_1} < X < \frac{a_2}{b_2}$$ and where $b_1, b_2 \leq d$
For example if $d=13$, and I want to approximate $X=0.15$, I can approximate it with as $1/7 < X < 2/13$.
The most straightforward idea is to generate all possible fractions $d^2$ and select the most suitable one. But it is too slow and after some investigation I found two potential methods:
- continuous fractions, which actually gives a really good approximation iteratively, but does not takes into account my denominator.
- farey sequence, which sounds really promising so I will explain what I tried with it.
It looks like this is exactly what I need. The only problem is that it allows to approximate only the number from $[0, 1]$, but in my opinion this is not a problem because I can just map a value $X$ to $[0, 1]$ get a result and scale the result.
There is an algorithm how to generate the next term of the sequence knowing the previous two. The problem is that potentially I have to generate half of the sequence before finding the right one (half because if $X > 0.5$ I am starting from the back, otherwise from the front). It would be super amazing if I can just skip some of the elements (being able to generate $n$th element without knowing all $n-1$).
My question is: how can I approximate a decimal with two fractions where denominator is less or equal to $d$ in less than $O(d)$ amount of operations? I am looking for the best approximation.
P.S. people are suggesting that I eliminated the correct path and continuous fractions are the right tool. I am not sure how can I use it here. For example I want to approximate $0.25$ with $d=113$. My continuous fraction will be just $1/4$ and I have no idea what steps should I use to end up with a correct answers:
$$\frac{28}{113} < 0.25 < \frac{28}{111}$$
To be clear, this is how I understand the question: Given a number $X$ and a bound $b_0$, find the following rational numbers:
You're right that continued fractions aren't helpful in the case where $X$ is a rational number with denominator smaller than $b_0$, as in your example where $X=\frac14$. I'll present a solution for that case only. If $X$ has a large denominator, or is irrational, then I think continued fractions will be more useful for you.
Suppose $X=\frac{p}{q}$, with $q<b_0$. Then we know that $b_1$ and $b_2$ must be larger than $b_0-q$. Indeed, if $\frac{a_1}{b_1}<X$ with $b_1\leq b_0-q$, then $\frac{a_1+p}{b_1+q}$ is still less than $X$, and closer than $\frac{a_1}{b_1}$. A similar argument applies for the upper bound.
Consider the set of number numbers $S=\{b_0-q+1, b_0-q+2,\ldots,b_0\}$. These numbers form a complete set of residues modulo $q$. Let $b_1$ be the element of $S$ congruent to $1$, and let $b_2$ be the element of $S$ congruent to $-1$, both modulo $q$. Now let $a_1=p\cdot\frac{b_1-1}{q}$, and let $a_2=p\cdot\frac{b_2+1}{q}$
I claim that these choices of $a_1,b_1,a_2,b_2$ satisfy the stated conditions. Indeed,
$X-\frac{a_1}{b_1} = \frac{p}{q}-\frac{p(b_1-1)}{qb_1} = \frac{1}{qb_1}>0$
and
$\frac{a_2}{b_2}-X = \frac{p(b_2+1)}{qb_2}-\frac{p}{q} = \frac{1}{qb_2}>0$,
so we have the right inequalities, at least.
Proving that they are optimal will take a little more work, but I'm pretty sure this is the solution you want...