Rounding to fraction 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). 
 A: 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
A: 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})$.
