This is an update to an old node by esteemed monk tilly.
Say you have a decimal number like 0.421875 and you want to print it as a fraction. Now, "obviously", that's equal to 27/64, but how do you write a program to find that out? The best way is with the method of continued fractions, and the surprise is that it's dead simple. This program produces a sequence of fractions that are increasingly good approximations of the input number.
use Math::BigInt; use Math::BigRat; die 'number required' unless @ARGV == 1; my $x = my $y = Math::BigRat>new($ARGV[0])>babs(); my $h = my $k1 = Math::BigInt>new(1); my $k = my $h1 = Math::BigInt>new(0); while (1) { my $t = $y>as_int(); ($h, $h1) = ($t * $h + $h1, $h); ($k, $k1) = ($t * $k + $k1, $k); my $val = Math::BigRat>new($h, $k); my $err = $val  $x; printf "%s: %s / %s = %.16g (%.1g)\n", $t, $h, $k, $val, $err; $y = $t or last; $y = 1 / $y; } __END__ 0: 0 / 1 = 0 (0.4) 2: 1 / 2 = 0.5 (0.08) 2: 2 / 5 = 0.4 (0.02) 1: 3 / 7 = 0.4285714285714285 (0.007) 2: 8 / 19 = 0.4210526315789473 (0.0008) 3: 27 / 64 = 0.421875 (0)
Clearly, this code is much simpler than before. What's not obvious is that it always terminates with $h/$k exactly equal to $x. In practice, you probably want to stop the loop early, perhaps when $err is small enough or $k gets too big.
This algorithm can even tackle really obnoxious inputs like 0.49420098210293 (463051/936969).
You can do away with BigInt and BigRat and use ordinary numbers, but then the loop is no longer guaranteed to terminate. To be safe, maybe put in a limit on the maximum number of iterations.
The first number on each line, $t, is a term in the continued fraction representation. You can mostly ignore it, but it has some interesting mathematical properties. For example, if you set $x to sqrt(2), all terms after the first should be 2, but only the first 18 are correct because of roundoff.


Replies are listed 'Best First'.  

Re: decimal to fraction
by vr (Friar) on Sep 12, 2017 at 12:49 UTC  
by huck (Vicar) on Sep 12, 2017 at 13:07 UTC  
by pryrt (Priest) on Sep 12, 2017 at 13:47 UTC  
Re: decimal to fraction
by Laurent_R (Canon) on Sep 24, 2017 at 11:48 UTC  
by no_slogan (Deacon) on Sep 24, 2017 at 15:30 UTC 