Re: Re: Percentages to Fractions

Did you look at the link provided to Continued Fractions?

Sure, the approach there is more complex, but the method provided does a better job of producing a rapidly converging sequence of fractional approximations than yours does. Modifying it to stop when the next approximation is more than 100, I produce the following output on your dataset:

2/57  =  0.0350877192982456
1/27  =  0.037037037037037
3/77  =  0.038961038961039
3/73  =  0.0410958904109589
4/93  =  0.043010752688172
4/87  =  0.0459770114942529
1/21  =  0.0476190476190476
4/69  =  0.0579710144927536
3/44  =  0.0681818181818182
6/77  =  0.0779220779220779
7/20  =  0.35
37/100  =  0.37
39/100  =  0.39
41/100  =  0.41
43/100  =  0.43
23/50  =  0.46
12/25  =  0.48
29/50  =  0.58
17/25  =  0.68
39/50  =  0.78
[download]

For half of them it found the actual fraction. For the other half it was never off by more than 0.0001. If you let it go to a denominator of 1000, it correctly identified every fraction, and put it in lowest terms.

(There are other tricks that I used there, like a GCD algorithm that is completely general and more efficient than trial division.)

Comment on Re: Re: Percentages to Fractions Download Code

Replies are listed 'Best First'.
Re: Re: Re: Percentages to Fractions by ysth (Canon) on Feb 04, 2004 at 00:24 UTC
++tilly. Here's what my try does for (1+5**.5)/2 (with the 999 limit removed): $ perl fract.pl 1.61803398874989 2/1 err=0.38196601125011 3/2 err=0.11803398874989 5/3 err=0.0486326779167767 8/5 err=0.0180339887498899 13/8 err=0.00696601125010998 21/13 err=0.0026493733652746 34/21 err=0.00101363029772905 55/34 err=0.00038692992636058 89/55 err=0.000147829431928148 144/89 err=5.6460660002422e-05 233/144 err=2.15668056655627e-05 377/233 err=8.23767692859079e-06 610/377 err=3.14652862454246e-06 987/610 err=1.20186464402927e-06 1597/987 err=4.59071791913956e-07 2584/1597 err=1.75349764708344e-07 4181/2584 err=6.69776640815911e-08 6765/4181 err=2.55831835715981e-08 10946/6765 err=9.77191327855564e-09 17711/10946 err=3.73253206120694e-09 28657/17711 err=1.42570710792711e-09 46368/28657 err=5.44565059712454e-10 75025/46368 err=2.08012052027584e-10 121393/75025 err=7.94468935083614e-11 196418/121393 err=3.03526093148321e-11 317811/196418 err=1.15869536188029e-11 514229/317811 err=4.43245440351347e-12 832040/514229 err=1.68642877440561e-12 1346269/832040 err=6.50812737035267e-13 2178309/1346269 err=2.41806574763359e-13 3524578/2178309 err=9.9031893796564e-14 5702887/3524578 err=3.10862446895044e-14 9227465/5702887 err=1.86517468137026e-14 14930352/9227465 err=4.44089209850063e-16 [download] Lovely pattern! (Except that it wanders off into lala land after that last line...)	[reply] [d/l]

Replies are listed 'Best First'.

Re: Re: Re: Percentages to Fractions
by ysth (Canon) on Feb 04, 2004 at 00:24 UTC

tilly

Here's what my try does for (1+5**.5)/2 (with the 999 limit removed):

$ perl fract.pl 1.61803398874989
2/1             err=0.38196601125011
3/2             err=0.11803398874989
5/3             err=0.0486326779167767
8/5             err=0.0180339887498899
13/8            err=0.00696601125010998
21/13           err=0.0026493733652746
34/21           err=0.00101363029772905
55/34           err=0.00038692992636058
89/55           err=0.000147829431928148
144/89          err=5.6460660002422e-05
233/144         err=2.15668056655627e-05
377/233         err=8.23767692859079e-06
610/377         err=3.14652862454246e-06
987/610         err=1.20186464402927e-06
1597/987                err=4.59071791913956e-07
2584/1597               err=1.75349764708344e-07
4181/2584               err=6.69776640815911e-08
6765/4181               err=2.55831835715981e-08
10946/6765              err=9.77191327855564e-09
17711/10946             err=3.73253206120694e-09
28657/17711             err=1.42570710792711e-09
46368/28657             err=5.44565059712454e-10
75025/46368             err=2.08012052027584e-10
121393/75025            err=7.94468935083614e-11
196418/121393           err=3.03526093148321e-11
317811/196418           err=1.15869536188029e-11
514229/317811           err=4.43245440351347e-12
832040/514229           err=1.68642877440561e-12
1346269/832040          err=6.50812737035267e-13
2178309/1346269         err=2.41806574763359e-13
3524578/2178309         err=9.9031893796564e-14
5702887/3524578         err=3.10862446895044e-14
9227465/5702887         err=1.86517468137026e-14
14930352/9227465                err=4.44089209850063e-16
[download]

[reply]
[d/l]