Pathologically Eclectic Rubbish Lister  
PerlMonks 
comment on 
( #3333=superdoc: print w/replies, xml )  Need Help?? 
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.
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. In reply to decimal to fraction by no_slogan

