It is not difficult to see that any reduced fraction $\frac{p}{q}$
where $0 < p < q $ and both $p$ and $q$ have at most $N$
digits (where $N$ is a fixed integer) can be reconstructed
from its first $2N$ digits.


In other words, if we let
${\cal F}\_N= \lbrace (p,q) | 0 < p < q < {{10}^N} \rbrace $ and define
the mapping $ f : \ {\cal F}\_n \to { \mathbb N} $ by $ f(p,q)=$ integer\_part( $ \frac{10^{2N}p}{q} $) ,
then $f$ is injective. So there is a left inverse $g$, such that
$g(f(p,q))=(p,q)$ for any $(p,q) \in {\cal F}\_N$. What is the best way to compute
$g$ effectively ? There's always brute search, of course, but ...



Reconstructing a fraction from its first digits
Taking the continued fraction approximations of your decimal expansion until the denominators get larger than 10^N ought to work.


Edit: Let me add that you have to do a tiny bit more work to get the best rational approximants from the continued fraction, and that's probably the algorithm that should be used. See <http://en.wikipedia.org/wiki/Continued_fraction#Best_rational_approximations>


