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.

use Math::BigInt;
use Math::BigRat;
die 'number required' unless @ARGV == 1;
my $x = my $y = Math::BigRat->new($ARGV[0])->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)

[download]

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 round-off.

Replies are listed 'Best First'.
Re: decimal to fraction
by vr (Curate) on Sep 12, 2017 at 12:49 UTC
    In practice, you probably want to stop the loop early

    Just a note, for slow learners like me, that otherwise one always gets amazingly correct and on the same scale amazingly useless result :-):

    >perl rat.pl 0.49420098210293
0: 0 / 1 = 0 (-0.5)
2: 1 / 2 = 0.5 (0.006)
42: 42 / 85 = 0.4941176470588235 (-8e-005)
1: 43 / 87 = 0.4942528735632184 (5e-005)
1: 85 / 172 = 0.4941860465116279 (-1e-005)
1: 128 / 259 = 0.4942084942084942 (8e-006)
1: 213 / 431 = 0.494199535962877 (-1e-006)
3: 767 / 1552 = 0.494201030927835 (5e-008)
8: 6349 / 12847 = 0.4942009807737215 (-1e-009)
4: 26163 / 52940 = 0.4942009822440498 (1e-010)
2: 58675 / 118727 = 0.4942009820849512 (-2e-011)
3: 202188 / 409121 = 0.4942009821055385 (3e-012)
2: 463051 / 936969 = 0.4942009821029298 (-2e-016)
4869: 2254797507 / 4562511182 = 0.49420098210293 (8e-021)
5: 11274450586 / 22813492879 = 0.49420098210293 (-2e-021)
1: 13529248093 / 27376004061 = 0.49420098210293 (5e-023)
27: 376564149097 / 761965602526 = 0.49420098210293 (-2e-024)
1: 390093397190 / 789341606587 = 0.49420098210293 (1e-025)
13: 5447778312567 / 11023406488157 = 0.49420098210293 (-9e-028)
9: 49420098210293 / 100000000000000 = 0.49420098210293 (0)

    [download]

    Another surprising note, this little program produces more precise and more 'beautiful' (shorter) approximation, than a built-in verb for same purpose in my latest toy:

       2 x: 0.49420098210293
2993521666234 6057296069093

    [download]

    (cf. 463051/936969), and changing comparison tolerance (with 9!:19) doesn't help

[reply]
[d/l]
[select]

      Heh, While technically correct, IMHO this is kinda cheating 

      9: 49420098210293 / 100000000000000 = 0.49420098210293 (0)

      [download]
      and on the same scale amazingly useless result :-):

[reply]
[d/l]

        The numerator and denominator are mutually prime (no common factors), and thus the fraction is fully reduced. How else would you represent it as a fraction? 

        #!/usr/bin/env perl -l
use warnings;
use strict;

#####
# [id://56906] for quick gcf
sub gcf {
  my ($x, $y) = @_;
  ($x, $y) = ($y, $x % $y) while $y;
  return $x;
}

######

print gcf(49420098210293,100000000000000);  # prints 1

#####

use Math::Prime::Util qw/is_prime factor/;
print is_prime(49420098210293);             # not prime (I wasn't sure
+ when I started my answer)
local $, = 'x';
print factor(49420098210293);               # 113x4729x92481709
print factor(100000000000000);              # 2x2x2x2x2x2x2x2x2x2x2x2x
+2x2x5x5x5x5x5x5x5x5x5x5x5x5x5x5
# no common factors

        [download]
[reply]
[d/l]
Re: decimal to fraction
by etj (Priest) on Aug 28, 2024 at 21:05 UTC
    Here https://github.com/wlmb/Photonic/blob/5e94c0a940dff619492ac0a629eba26a4bff3259/lib/Photonic/Utils.pm#L294-L327 is a PDL-using implementation of the Lentz method of continuing fractions, algorithm from Numerical Recipes: 
    sub lentzCF {
    # continued fraction using lentz method Numerical Recipes
    # p. 171. Arguments are as, bs, maximum number of iterations and
    # smallness parameter
    # a0+b1/a1+b2+...
    my $as=shift;
    my $bs=shift;
    my $max=shift;
    my $small=shift;
    my $tiny=r2C(1.e-30);
    my $converged=0;
    my $fn=$as->slice(0);
    $fn=$tiny if all($fn==0);
    my $n=1;
    my ($fnm1, $Cnm1, $Dnm1)=($fn, $fn, r2C(0)); #previous coeffs.
    my ($Cn, $Dn); #current coeffs.
    my $Deltan;
    while($n<$max){
    $Dn=$as->slice($n)+$bs->slice($n)*$Dnm1;
    $Dn=$tiny if all($Dn==0);
    $Cn=$as->slice($n)+$bs->slice($n)/$Cnm1;
    $Cn=$tiny if all($Cn==0);
    $Dn=1/$Dn;
    $Deltan=$Cn*$Dn;
    $fn=$fnm1*$Deltan;
    last if $converged=$Deltan->approx(1, $small)->all;
    $fnm1=$fn;
    $Dnm1=$Dn;
    $Cnm1=$Cn;
    $n++;
    }
    $fn = $fn->slice("(0)");
    return wantarray? ($fn, $n): $fn;
}

    [download]
    Having made the odd tweak to it myself in passing, it continues to make me want to rewrite it in PP, which would probably go much quicker and would also allow pthreading for big batches of numbers. Probably it would live most naturally in either PDL::Math (the core), or maybe a PDL::NumericalAnalysis?
[reply]
[d/l]
Re: decimal to fraction
by Laurent_R (Canon) on Sep 24, 2017 at 11:48 UTC
    The same with Perl 6: 
    > say 0.421875.nude
(27 64)
>

    [download]
    Note: nude stands for numerator-denominator.
[reply]
[d/l]
[select]
      > 0.49420098210293.nude
(49420098210293 100000000000000)
> 0.49420098210293.Num().Rat(1e-15).nude
(463051 936969)

      [download]
      Yay Perl6. Took me a while to figure out the magic incantation, because the Perl6 documentation is nigh incomprehensible. Also, Rat() ignores the epsilon parameter if it's called on a rational. Sometimes, you'd like to find a fraction that's an approximation of another fraction without mashing it down to a float first.
[reply]
[d/l]

Back to Cool Uses for Perl