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

-
Is this a terminating or a repeating decimal? If it's a terminating decimal, it's a trivial solution: just multiply by 10^n for your numerator and stick the 10^n in the denominator and reduce. If it's a repeating decimal, just multiply p/q by 10^n and subtract p/q to get your repeating portion, then divide by (10^n - 1) to get your fraction. Then, reduce. Example: 0.123456789... Multiply by 10^9 to get 123456789.123456789... Subtract repeating portion to get 123456789 Divide by (10^9 - 1) to get 123456789/999999999 Reduce to 13717421/111111111 – Gabriel Benamy May 17 '10 at 16:59
@Gabriel, consider 1/7, which has decimal 0.142857 repeating. This can be reconstructed from just 0.14 if we let N=1. – j.c. May 17 '10 at 17:05
Ah, now I fully understand what the question is. So you're saying that every reduced a/b is unique up to the first 2n digits, where n = ceiling(log10(max(a,b))) (number of base-10 digits of the larger of a,b)? That's an interesting question... – Gabriel Benamy May 17 '10 at 17:10
This is reminiscent of the Berlekamp-Massey Algorithm which finds a LFSR (linear feedback shift register) of length $n$ producing a binary stream of length $2n$. I'll bet that you can modify to the B-M algorithm to solve this problem. en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm – Victor Miller May 17 '10 at 17:22

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

-
+1 for continued fractions. From this, you should be able to easily reproduce a simple poly(N)-time algorithm, which furthermore can be used to easily obtain improved approximations at each step without having to 'unravel' the continued fraction anew at each stage (i.e. by not explicitly formulating them as continued fractions). – Niel de Beaudrap May 17 '10 at 19:09
What would happen if I gave the algorithm, say, .19, which is NOT generated by any a/b where a,b < 10? – Gabriel Benamy May 18 '10 at 22:27
You'll get the closest approximation possible with a,b<10. In the case of 0.19, the approximants are 1/5, 1/(5+1/3)=3/16, 1/(5+1/(3+1))=4/21, 1/(5+1/(3+1/(1+1/4)))=19/100. Try playing around with maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/cfCALC.html – j.c. May 18 '10 at 23:57
Note that my comment refers to the "best rational approximation" algorithm in my edited answer, and not the original continued fraction truncation algorithm. Try e.g. 0.08 whose continued fraction truncation would be 0 (next convergent is 1/12), but whose best approximation (with a,b strictly <10) is really 1/9. – j.c. May 19 '10 at 0:13

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

-

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
-
What do you expect the upper bound on the run-time of this algorithm would be? It seems to me that if the number is (10^N - 2)/(10^N - 1), we get a sequence of lower bounds 1, 1/2, 2/3, 3/4, 4/5, ... which would take exponentially long to converge! – Niel de Beaudrap May 17 '10 at 17:22
The length of the algorithm is exactly equal to the sum of all the numbers occurring in the continued fraction expansion of 0.282051282. This algorithm can certainly be improved, to directly produce the sub-sequence 0/1, 1/3, 1/4, 2/7, 11/39, which is just the continued fraction expansion of 0.282051282. So my answer is not that different from jc's answer. – André Henriques May 17 '10 at 19:32
@André Henriques: No, your algorithm does not take the same time; it is not even poly-time equivalent, as is evident by the example I give above. Specifically: in the case of 99998/99999, where continued fractions stops in just two iterations (precisely 1/1 and 99998/99999). While this is indeed a subsequence of the almost-hundred-thousand-long sequence of values 1/1, 1/2, 2/3, ..., 99998/99999 obtained by your method, the two processes are not meaningfully equivalent. Producing a 'supersequence' is not sufficient for algorithmic equivalence. – Niel de Beaudrap May 17 '10 at 20:37
Interpret "can certainly be improved" in my above comment to mean "can be replaced by a different algorithm". – André Henriques May 18 '10 at 6:41

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

-