Reconstructing a fraction from its first digits 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 ...
 A: Henry Pollak has written a nice series of articles about how given a positive decimal one can construct a rational fraction that is approximately equal to the given decimal number. The first of these articles appeared in COMAP's (Consortium for Mathematics and Its Applications) newsletter Consortium, and can be found at this link:
http://webmail.comap.com/www.comap.com/pdf/749/Cons92.pdf
while the second article is here:
http://webmail.comap.com/www.comap.com/pdf/1004/C95.pdf
and the last article:
http://ns.comap.com/www.comap.com/pdf/1028/Con96.pdf
A: 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
A: Say I have the number x=0.282051282, and I want to know which fraction that is.
Here is an algorithm:


*

*0/1 < x < 1/0


add the numerators and add the denominators to get 1/1.
Compare x to 1/1:


*

*0/1 < x < 1/1


add the numerators and add the denominators to get 1/2.
Compare x to 1/2:


*

*0/1 < x < 1/2


add the numerators and add the denominators to get 1/3.
Compare x to 1/3:


*

*0/1 < x < 1/3


add the numerators and add the denominators to get 1/4.
Compare x to 1/4:


*

*1/4 < x < 1/3


add the numerators and add the denominators to get 2/7.
Compare x to 2/7:


*

*1/4 < x < 2/7


add the numerators and add the denominators to get 3/11.
Compare x to 3/11:


*

*3/11 < x < 2/7


add the numerators and add the denominators to get 5/18.
Compare x to 5/18:


*

*5/18 < x < 2/7


add the numerators and add the denominators to get 7/25.
Compare x to 7/25:


*

*7/25 < x < 2/7


add the numerators and add the denominators to get 9/32.
Compare x to 9/32:


*

*9/32 < x < 2/7


add the numerators and add the denominators to get 11/39.
Compare x to 11/39:


*

*x = 11/39

A: The nicest answers to your fraction come from taking the partial convergents to the continued fraction expansion for the decimal.
