How to convert a float to a fraction is a topic in Knuth's Concrete Mathematics. It is based on a wierd operation which one could call "children's fractional addition" (i.e. the way a child might add fractions). This is

 a     c      a+c
--- + --- => -----
 b     d      b+d
[download]

This is a very common children's mistake, and the result (until I saw this trick) is useful for nothing. But to find the sequence of best approximating fractions to any number, here is a bracketing algorithm based on the above operation which is fast and easy: Algorithm to approximate x (a positive real number) Start with two fractions:

a/b = 0/1
c/d = 1/0 [This is infinity, larger than any number]
[download]

create a third fraction e/f = (a+c)/(b+d) by "children adding" the two fractions Note: Do not simplify any fraction in this process. This new number will always be between the first two fractions. Discard one of the original two fractions, and replace it with the new fraction in such a way that the two fractions that are kept, still bracket the x. Keep doing this and you will get a sequence of fractions that quickly squeeze the x.

It can be shown that no fraction with a smaller denominator can get closer than fractions in this sequence.

frac(3.14159265358979);
sub frac
{ my ($x,$a,$b,$c,$d,$e,$f) = (@_,0,1,1,0,1,1);
  while ($f<1000)
  { if ($e<$x*$f) { ($a,$b) = ($e,$f) }
    else          { ($c,$d) = ($e,$f) }
    ($e,$f) = ($a+$c, $b+$d);
    print "$a/$b < $x < $c/$d; => $e/$f\n";
} }
[download]

Produces the output

1/1 < 3.14159265358979 < 1/0; => 2/1
2/1 < 3.14159265358979 < 1/0; => 3/1
3/1 < 3.14159265358979 < 1/0; => 4/1
3/1 < 3.14159265358979 < 4/1; => 7/2
3/1 < 3.14159265358979 < 7/2; => 10/3
3/1 < 3.14159265358979 < 10/3; => 13/4
3/1 < 3.14159265358979 < 13/4; => 16/5
3/1 < 3.14159265358979 < 16/5; => 19/6
3/1 < 3.14159265358979 < 19/6; => 22/7
3/1 < 3.14159265358979 < 22/7; => 25/8
25/8 < 3.14159265358979 < 22/7; => 47/15
47/15 < 3.14159265358979 < 22/7; => 69/22
69/22 < 3.14159265358979 < 22/7; => 91/29
91/29 < 3.14159265358979 < 22/7; => 113/36
113/36 < 3.14159265358979 < 22/7; => 135/43
135/43 < 3.14159265358979 < 22/7; => 157/50
157/50 < 3.14159265358979 < 22/7; => 179/57
179/57 < 3.14159265358979 < 22/7; => 201/64
201/64 < 3.14159265358979 < 22/7; => 223/71
223/71 < 3.14159265358979 < 22/7; => 245/78
245/78 < 3.14159265358979 < 22/7; => 267/85
267/85 < 3.14159265358979 < 22/7; => 289/92
289/92 < 3.14159265358979 < 22/7; => 311/99
311/99 < 3.14159265358979 < 22/7; => 333/106
333/106 < 3.14159265358979 < 22/7; => 355/113
333/106 < 3.14159265358979 < 355/113; => 688/219
688/219 < 3.14159265358979 < 355/113; => 1043/332
1043/332 < 3.14159265358979 < 355/113; => 1398/445
1398/445 < 3.14159265358979 < 355/113; => 1753/558
1753/558 < 3.14159265358979 < 355/113; => 2108/671
2108/671 < 3.14159265358979 < 355/113; => 2463/784
2463/784 < 3.14159265358979 < 355/113; => 2818/897
2818/897 < 3.14159265358979 < 355/113; => 3173/1010
[download]