decimal to fraction

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.

Comment on decimal to fraction Download Code

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]
Re^2: decimal to fraction by huck (Prior) on Sep 12, 2017 at 13:07 UTC
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]
Re^3: decimal to fraction by pryrt (Abbot) on Sep 12, 2017 at 13:47 UTC
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 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]
Re^2: decimal to fraction by no_slogan (Deacon) on Sep 24, 2017 at 15:30 UTC
`> 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]


Come for the quick hacks, stay for the epiphanies.
	PerlMonks