Re: Percentages to Fractions (The good, the bad and the **rediculous**)

Ok, here's my rediculous approach that will give the exact answer... Thanks to tilly for the 'gcd' function, that was great! :-D

use strict;
use warnings;

while (<DATA>) {
    chomp;

    my $a = $_;
    $a =~ s/^\d?\.0*?//;     # strip 0.0 part from 0.035

    my $b = length($_) - 2;  # how many zero's we need
                             # assume in 0.0x form
    my $c = 10 ** $b;

    my $gcd = gcd($a, $c);
    $a /= $gcd;
    $c /= $gcd;

    print $_, "\t", "$a/$c", "\n";
}

# ---- borrowed from tilly's code ----
sub gcd {
  my ($n, $m) = @_;
  while ($m) {
    my $k = $n % $m;
    ($n, $m) = ($m, $k);
  }
  return $n;
}

__DATA__
0.035
0.037
0.039
0.041
0.043
0.046
0.048
0.058
0.068
0.078
0.35
0.37
0.39
0.41
0.43
0.46
0.48
0.58
0.68
0.78
[download]

And the output -

0.035   7/200
0.037   37/1000
0.039   39/1000
0.041   41/1000
0.043   43/1000
0.046   23/500
0.048   6/125
0.058   29/500
0.068   17/250
0.078   39/500
0.35    7/20
0.37    37/100
0.39    39/100
0.41    41/100
0.43    43/100
0.46    23/50
0.48    12/25
0.58    29/50
0.68    17/25
0.78    39/50
[download]

Comment on Re: Percentages to Fractions (The good, the bad and the rediculous) Select or Download Code

Replies are listed 'Best First'.
Re: Re: Percentages to Fractions (The good, the bad and the rediculous) by monad (Initiate) on Feb 10, 2004 at 12:20 UTC
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]	[reply] [d/l] [select]
Re: Re: Percentages to Fractions (The good, the bad and the rediculous) by eric256 (Parson) on Apr 13, 2004 at 22:35 UTC
Letting GCD do all your work realy is quite brilliant. Kinda using the defintion of a decimal as the solution. ___________ Eric Hodges	[reply]