0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Continued fractions are the right tool. $\endgroup$ – André Nicolas Jun 12 '15 at 4:45
  • $\begingroup$ Definitely continued fractions. $\endgroup$ – Thomas Andrews Jun 12 '15 at 4:45
  • $\begingroup$ @ThomasAndrews I updated my question with the reason why I gave up idea of continued fractions. $\endgroup$ – Salvador Dali Jun 12 '15 at 5:27
  • $\begingroup$ I consider $1/4$ as an excellent "approximation." The usual aim is to get good approximations with minimal denominator. $\endgroup$ – André Nicolas Jun 12 '15 at 5:31
  • $\begingroup$ @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. $\endgroup$ – Salvador Dali Jun 12 '15 at 5:41
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Salvador Dali Jun 12 '15 at 4:57
  • $\begingroup$ @SalvadorDali But this leaves Linus' essential questions: How good do you want the approximations to be? Must the process pick the best possible fractions? $\endgroup$ – Travis Jun 12 '15 at 5:26
  • $\begingroup$ @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. $\endgroup$ – Salvador Dali Jun 12 '15 at 5:28

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.