CUFP
no_slogan
<p>This is an update to an [id://41961|old node] by esteemed monk [tilly].</p>
<p>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 [wp://continued fraction|continued fractions], and the surprise is that it's <i>dead simple</i>. This program produces a sequence of fractions that are increasingly good approximations of the input number.</p>
<code>
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)
</code>
<p>Clearly, this code is much simpler than before. What's not obvious is that it always terminates with <tt>$h/$k</tt> exactly equal to <tt>$x</tt>. In practice, you probably want to stop the loop early, perhaps when <tt>$err</tt> is small enough or <tt>$k</tt> gets too big.</p>
<p>This algorithm can even tackle really obnoxious inputs like 0.49420098210293 (463051/936969).</p>
<p>You can do away with <tt>BigInt</tt> and <tt>BigRat</tt> 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.</p>
<p>The first number on each line, <tt>$t</tt>, 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 <tt>$x</tt> to sqrt(2), all terms after the first should be 2, but only the first 18 are correct because of round-off.</p>