3
$\begingroup$

If I write the number 0.333333, you will immediately think to $1/3$. Somehow 0.333333 has been "rounded" to $1/3$. I wonder if there is a general way to find such fraction. So let's formulate the problem in a precise way. I suppose here that all numbers are positive. Given a real $a$ and an integer $n$, I want to find the reduced fraction that is closest to $a$ with denominator less than $n$. So this fraction approximates the real with an error at most $1/n$. Is there an efficient algorithm to find it (other than brute forcing it by checking all possible denominators).

$\endgroup$
2
$\begingroup$

Looking at the proof for Dirichlet's approximation theorem, the one which uses pigeonhole principle, we can define $$a_i=i\cdot a - \left \lfloor i\cdot a \right \rfloor, i=0..n$$ thus each $a_i \in [0,1]$.

Then split $[0,1]$ into $n$ segments $[0,\frac{1}{n}]$,$[\frac{1}{n},\frac{2}{n}]$,$[\frac{2}{n}, \frac{3}{n}]$, ... $[\frac{n-1}{n},n]$, so we end up with $n$ segments and $n+1$ of $a_i, i=0..n$. According to the pigeonhole principle, two elements of $\{a_i\}$ will be within one such segment, i.e. $\exists i,j \in \{0,1,3,...,n\}, i \ne j$ (we can assume $j>i$) such that $$|a_j - a_i| < \frac{1}{n}$$ or $$\left|(j-i)a - (\left \lfloor j\cdot a \right \rfloor-\left \lfloor i\cdot a \right \rfloor) \right|<\frac{1}{n}$$

Then we note $\left \lfloor j\cdot a \right \rfloor-\left \lfloor i\cdot a \right \rfloor=m \in \mathbb{N}$ and $q=j-i < n, q \in \mathbb{N}$. As a result $$|q\cdot a - m| < \frac{1}{n}$$ or $$\left|a - \frac{m}{q}\right| < \frac{1}{n\cdot q} < \frac{1}{n}$$ I am not sure if this is the most efficient algorithm, because it's $O(n^2)$, although it may be improved with sorting to $O(n\ln{n})$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

I don't know what the best algorithm is, but assuming you are just working with rational numbers, then, turn it into an algebraic problem.

In this case it satisfies the equation,

\begin{equation} 10x - 3 = x \end{equation}

which is easily rewritten as \begin{equation} 9x = 3 \end{equation}

so that \begin{equation} x = \frac{3}{9} = \frac{1}{3} \end{equation}

If you are working with real numbers, I believe the best rational approximation is given by turning your real into a continued fraction, as is suggested in the comments: https://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You can start with a rational number but what you suggest is the standard way to convert a periodic decimal number into a fraction. This is not what I am looking for. In my example I mean really 0.333333 with six digits (not an infinity) which is not $1/3$. However, if you put $n$ to 1000 (so that the error will be less than $1/000$), the closest fraction to 0.333333 with denominator less than 1000 is $1/3$. $\endgroup$ – Olivier Esser Feb 3 '17 at 18:02
  • $\begingroup$ I have just fond that the programming language python has a function that does exactly that (limit_denominator). The source code has an interesting comment about the algorithm involved: svn.python.org/projects/python/trunk/Lib/fractions.py $\endgroup$ – Olivier Esser Feb 3 '17 at 18:26

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.