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