Re: Percentages to Fractions

Not to discourage you, but you really need a more efficient algorithm. Your algorithm is O^2 at best, and as the need for accuracy increases, the performance penalty gets greater and greater.

Here's an alternative very fast and efficient log(log(O)) algorithm: A fraction can be expressed as the sum (or difference) of a series of fractions:

0.35 = 1/28 - 1/6 - 1/60 = 7/20
0.35 = int (1/0.35) - int (1/(1 - int(1/0.35))) ...
[download]

Which is a perfect candidate for a recursive function. I implement the following demo to show how this can be done. Hopefully you might find it useful. :-)

use strict;
use warnings;

while (<DATA>) {
    chomp;

    my ($den, $div, $error) = fraction($_);

    print "$_\t$den/$div\n";
}

sub fraction
{
    my $value = shift;

    my $a = 1;
    my $b = int(1 / $value);
    my $c = (1 / $b) - $value;  # error

    return ($a, $b, $c) if $c < 0.0005;

    my ($d, $e, $f) = fraction($c);

    my $g = $a * $e - $d * $b;
    my $h = $b * $e;
    
    for (2,3,5,7) { # reduces 2/4 => 1/2, 3/27 => 1/9, etc.
        ($g, $h) = reduce($g, $h, $_);
    }

    return ($g,
            $h,
            $f);
}

sub reduce
{
    my ($a, $b, $base) = @_;
    while ($a % $base == 0 && $b % $base == 0) {
        $a = $a / $base;
        $b = $b / $base;
    }
    return ($a, $b);
}



__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   1/27
0.039   974/24975
0.041   41/1000
0.043   1/23
0.046   596/12957
0.048   479/9980
0.058   1197/20638
0.068   277/4074
0.078   175/2244
0.35    7/20
0.37    57/154
0.39    6311/16182
0.41    4961/12100
0.43    43/100
0.46    23/50
0.48    47/98
0.58    2081/3588
0.68    151/222
0.78    103/132
[download]

Comment on Re: Percentages to Fractions Select or Download Code

Replies are listed 'Best First'.
Re: Re: Percentages to Fractions by tilly (Archbishop) on Feb 03, 2004 at 23:00 UTC
Did you look at the link provided to Continued Fractions? Sure, the approach there is more complex, but the method provided does a better job of producing a rapidly converging sequence of fractional approximations than yours does. Modifying it to stop when the next approximation is more than 100, I produce the following output on your dataset: `2/57 = 0.0350877192982456 1/27 = 0.037037037037037 3/77 = 0.038961038961039 3/73 = 0.0410958904109589 4/93 = 0.043010752688172 4/87 = 0.0459770114942529 1/21 = 0.0476190476190476 4/69 = 0.0579710144927536 3/44 = 0.0681818181818182 6/77 = 0.0779220779220779 7/20 = 0.35 37/100 = 0.37 39/100 = 0.39 41/100 = 0.41 43/100 = 0.43 23/50 = 0.46 12/25 = 0.48 29/50 = 0.58 17/25 = 0.68 39/50 = 0.78` [download] For half of them it found the actual fraction. For the other half it was never off by more than 0.0001. If you let it go to a denominator of 1000, it correctly identified every fraction, and put it in lowest terms. (There are other tricks that I used there, like a GCD algorithm that is completely general and more efficient than trial division.)	[reply] [d/l]
Re: Re: Re: Percentages to Fractions by ysth (Canon) on Feb 04, 2004 at 00:24 UTC
++tilly. Here's what my try does for (1+5**.5)/2 (with the 999 limit removed): $ perl fract.pl 1.61803398874989 2/1 err=0.38196601125011 3/2 err=0.11803398874989 5/3 err=0.0486326779167767 8/5 err=0.0180339887498899 13/8 err=0.00696601125010998 21/13 err=0.0026493733652746 34/21 err=0.00101363029772905 55/34 err=0.00038692992636058 89/55 err=0.000147829431928148 144/89 err=5.6460660002422e-05 233/144 err=2.15668056655627e-05 377/233 err=8.23767692859079e-06 610/377 err=3.14652862454246e-06 987/610 err=1.20186464402927e-06 1597/987 err=4.59071791913956e-07 2584/1597 err=1.75349764708344e-07 4181/2584 err=6.69776640815911e-08 6765/4181 err=2.55831835715981e-08 10946/6765 err=9.77191327855564e-09 17711/10946 err=3.73253206120694e-09 28657/17711 err=1.42570710792711e-09 46368/28657 err=5.44565059712454e-10 75025/46368 err=2.08012052027584e-10 121393/75025 err=7.94468935083614e-11 196418/121393 err=3.03526093148321e-11 317811/196418 err=1.15869536188029e-11 514229/317811 err=4.43245440351347e-12 832040/514229 err=1.68642877440561e-12 1346269/832040 err=6.50812737035267e-13 2178309/1346269 err=2.41806574763359e-13 3524578/2178309 err=9.9031893796564e-14 5702887/3524578 err=3.10862446895044e-14 9227465/5702887 err=1.86517468137026e-14 14930352/9227465 err=4.44089209850063e-16 [download] Lovely pattern! (Except that it wanders off into lala land after that last line...)	[reply] [d/l]