# How can I approximate a decimal with two fractions where denominator is less or equal to $d$

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}$$

• Continued fractions are the right tool. – André Nicolas Jun 12 '15 at 4:45
• Definitely continued fractions. – Thomas Andrews Jun 12 '15 at 4:45
• @ThomasAndrews I updated my question with the reason why I gave up idea of continued fractions. – Salvador Dali Jun 12 '15 at 5:27
• I consider $1/4$ as an excellent "approximation." The usual aim is to get good approximations with minimal denominator. – André Nicolas Jun 12 '15 at 5:31
• @AndréNicolas Yes, I have nothing against it, the problem is that $1/4 = 0.25$ and I am looking for such fractions that $\frac{a_1}{b_1} < X < \frac{a_2}{b_2}$. Basically any denominator less or equal to some predefined one. – Salvador Dali Jun 12 '15 at 5:41

To be clear, this is how I understand the question: Given a number $X$ and a bound $b_0$, find the following rational numbers:

• $\frac{a_1}{b_1}=\max\{\frac{a}{b}:\frac{a}{b}<X \text{ and } b\leq b_0\}$
• $\frac{a_2}{b_2}=\min\{\frac{a}{b}:\frac{a}{b}>X \text{ and } b\leq b_0\}$

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

How tight must the approximations be? Do $\frac{a_1}{b_1}$ and $\frac{a_2}{b_2}$ have to be the closest ones to $X$?

One (very rough) approximation is to simply convert $X$ into a fraction with a denominator of $10^n$ with $n$ being the number of digits of $X$. In the case of an infinite decimal we just need to round to some decimal place. Then, we divide both the numerator and denominator by $\frac{10^n}{d}$ and floor the numerator to get the lower bound and ceiling the numerator to get the upper bound.

• I am not looking for a very rough approximation. Because I can otherwise I can just approximate it with $0/d$ < X < $(d*x+1)/d$. – Salvador Dali Jun 12 '15 at 4:57
• @SalvadorDali But this leaves Linus' essential questions: How good do you want the approximations to be? Must the process pick the best possible fractions? – Travis Jun 12 '15 at 5:26
• @Travis sorry, I updated my original question. I am looking for the best possible approximation. Out of all fractions with denominator less or equal to $d$ I want to find the best. – Salvador Dali Jun 12 '15 at 5:28