Convert decimal number to rational
The task is to write a program to transform a decimal number into fraction in lowest terms.
For transform a decimal to a fraction, previously we have to know what type is the decimal number, here are some examples
'Examples of types decimal numbers:
67 / 74 = 0.9054054 >>> Mixed decimal number
42 / 81 = 0.518518 >>> Pure decimal number
3/4 = 0.75 >>> Exact decimal number
Option >>>
4527027/ 5000000 = 0.9054054
259259/ 500000 = 0.518518
3/ 4 = 0.75
Ada
Specification of a procedure Real_To_Rational, which is searching for the best approximation of a real number. The procedure is generic. I.e., you can instantiate it by your favorite "Real" type (Float, Long_Float, ...).
<lang Ada>generic
type Real is digits <>;
procedure Real_To_Rational(R: Real;
Bound: Positive;
Nominator: out Integer;
Denominator: out Positive);</lang>
The implementation (just brute-force search for the best approximation with Denominator less or equal Bound):
<lang Ada>procedure Real_To_Rational (R: Real;
Bound: Positive;
Nominator: out Integer;
Denominator: out Positive) is
Error: Real;
Best: Positive := 1;
Best_Error: Real := Real'Last;
begin
if R = 0.0 then
Nominator := 0;
Denominator := 1;
return;
elsif R < 0.0 then
Real_To_Rational(-R, Bound, Nominator, Denominator);
Nominator := - Nominator;
return;
else
for I in 1 .. Bound loop
Error := abs(Real(I) * R - Real'Rounding(Real(I) * R));
if Error < Best_Error then
Best := I;
Best_Error := Error;
end if;
end loop;
end if;
Denominator := Best;
Nominator := Integer(Real'Rounding(Real(Denominator) * R));
end Real_To_Rational;</lang>
The main program, called "Convert_Decimal_To_Rational", reads reals from the standard input until 0.0. It outputs progressively better rational approximations of the reals, where "progressively better" means a larger Bound for the Denominator:
<lang Ada>with Ada.Text_IO; With Real_To_Rational;
procedure Convert_Decimal_To_Rational is
type My_Real is new Long_Float; -- change this for another "Real" type
package FIO is new Ada.Text_IO.Float_IO(My_Real); procedure R2R is new Real_To_Rational(My_Real);
Nom, Denom: Integer; R: My_Real;
begin
loop
Ada.Text_IO.New_Line;
FIO.Get(R);
FIO.Put(R, Fore => 2, Aft => 9, Exp => 0);
exit when R = 0.0;
for I in 0 .. 4 loop
R2R(R, 10**I, Nom, Denom);
Ada.Text_IO.Put(" " & Integer'Image(Nom) &
" /" & Integer'Image(Denom));
end loop;
end loop;
end Convert_Decimal_To_Rational; </lang>
Finally, the output (reading the input from a file):
> ./convert_decimal_to_rational < input.txt 0.750000000 1 / 1 3 / 4 3 / 4 3 / 4 3 / 4 0.518518000 1 / 1 1 / 2 14 / 27 14 / 27 14 / 27 0.905405400 1 / 1 9 / 10 67 / 74 67 / 74 67 / 74 0.142857143 0 / 1 1 / 7 1 / 7 1 / 7 1 / 7 3.141592654 3 / 1 22 / 7 22 / 7 355 / 113 355 / 113 2.718281828 3 / 1 19 / 7 193 / 71 1457 / 536 25946 / 9545 -0.423310825 0 / 1 -3 / 7 -11 / 26 -69 / 163 -1253 / 2960 31.415926536 31 / 1 157 / 5 377 / 12 3550 / 113 208696 / 6643 0.000000000
BASIC
<lang qbasic> 'Program to transform a decimal to a fraction 'LRCVS 11.06.11
'program to transform a decimal number to fraction declare sub exacto (a$) declare sub puro (a$, b$()) declare sub mixto (a$, b$()) declare function factor (j , k ) as integer
dim as integer l, r, s, t, k, w1, i, m, x, ll, pp, ps, u, v, j
dim as string a, c, d, a2
dim y () as string dim w2 () as string
cls input "Decimal number = ";a$ a2$ = a$ print if instr(a$,".") = 0 then print "It's not a decimal number " : goto 100 cls l = len(a$)
for r = 1 to l for s = 1 to l if s + r = l + 2 then exit for k = k + 1 next s next r
w1 = k redim y$(w1) redim b$(w1)
k = 0 for r = 1 to l for s = 1 to l c$ = mid$(a$,r,s) if s + r = l + 2 then exit for if len(c$) <= int(l/2) then k = k + 1 : y$(k) = c$ next s next r t = 0
for r = 1 to k i = 0 f = 0 x = 0 m = 0 if i = 0 then i = instr(a$,y$(r)):x = 1 for s = 1 to len(a$) if x = 1 then f = instr(s,a$,y$(r)) if x = 1 and f > m then m = f next s
h = 0 k = 0 for n = i to m step len(y$(r)) if h = 0 and mid$(a$,n,len(y$(r))) = y$(r) then k = k + 1 else h = 1 next n if k > 1 then t = t + 1 :b$(t) = y$(r) next r
for r = 1 to w1 for s = r + 1 to w1 if b$(r) = b$(s) then b$(s) = "" next s next r
print "decimal number = ";a$ print
ll = len(a$) pp = instr(a$,".") d$ = mid$(a$,pp+1,ll) ps = instr(d$,b$(1)) if ps = 0 then
print "Decimal number exact"
print
call exacto (a$)
end if
if ps = 1 then
print "Decimal number pure"
print
call puro (a$, b$())
end if
if ps > 1 then
print "Decimal number mix"
print
call mixto (a$, b$())
end if
100: print print "End" sleep end
':::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: sub exacto (a as string) dim as integer b, c, d, g, may, j, k, l, r, s, u, v, w, f dim as string z, h, g1 b = len(a$) c = instr(a$,".") d = b - c g = int(val(a$)) h$ = right$(a$, b - c)
may = 0 j = 10^d k = val(h$) for n = 9 to 1 step - 1 if j mod (1*(10^n)) = 0 and k mod (1*(10^n)) = 0 then j = j/(1*(10^n)) : k = k/(1*(10^n)) :exit for next n l = factor (j,k) u = k/l v = j/l w = (g * v) + u print print w;"/";v ;" = " ;w/v
end sub
':::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: sub puro (a as string, b() as string) dim as integer b2, c, d, g, may, j, k, l, u, v, w, f, lr,x5 dim as string z, h, g1, x, a3
z$ = b$(1) x5 = int(val(a$)) lr = len (z$) b2 = len (a$) c = instr (a$,".") g = int (val(a$)) b2 = len(z$) + 1 + len(str$(g)) a3$ = str$(g) + "." + z$ h$ = right$(a3$, b2 - c)
may = 0 x$ = "" for n = 1 to lr x$ = x$ + "9" next n
j = val(x$) k = val(h$)
for n = 9 to 1 step - 1 if j mod (1*(10^n)) = 0 and k mod (1*(10^n)) = 0 then j = j/(1*(10^n)) : k = k/(1*(10^n)) :exit for next n l = factor (j,k) u = k/l v = j/l w = (g * v) + u print w;"/";v ;" = ";w/v print print "Option >>> " call exacto (a$)
end sub
':::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: sub mixto (a as string, b() as string)
dim as integer b3, c, d, g, j, k, l, u, v, w, f, lr, lz, ly, x5 dim as string z, h, g4, g7, x, y
z$ = b$(1) x5 = int(val(a$)) w = instr(a$, z$) v = instr(a$,".") y$ = mid$(a$,v+1,w-v-1) lz = len(z$) ly = len(y$) b3 = (val(y$)*(9*(10^ly))) + ((1*(10^ly))* (val(z$))) c = (9*(10^ly))*(1*(10^ly)) j = b3 k = c for n = 9 to 1 step - 1 if j mod (1*(10^n)) = 0 and k mod (1*(10^n)) = 0 then j = j/(1*(10^n)) : k = k/(1*(10^n)): exit for next n l = factor (b3,c) u = k/l v = j/l if x5 <> 0 then print (x5*v)+ u;"/";u ;" = ";((x5*v)+ u)/u else print v;"/";u;" = "; v/u print print "Option >>> " call exacto (a$) end sub ':::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: function factor (j as integer, k as integer) as integer dim as integer may, n, s, r, l5, j5, k5 may = 0 l5 = 1 j5 = j k5 = k for n = 9 to 1 step - 1 if j5 mod (1*(10^n)) = 0 and k5 mod (1*(10^n)) = 0 then j5 = j5/(1*(10^n)) : k5 = k5/(1*(10^n)): exit for next n if j5 > k5 then may = j5 else may = k5 for n = may to 1 step - 1
r = (j5 mod n) s = (k5 mod n) if r = 0 and s = 0 then l5 = n :exit for
next n factor = l5 end function end</lang>
C
Since the intention of the task giver is entirely unclear, here's another version of best rational approximation of a floating point number. It's somewhat more rigorous than the Perl version below, but is still not quite complete.<lang C>#include <stdio.h>
- include <stdlib.h>
- include <math.h>
- include <stdint.h>
/* f : number to convert.
* num, denom: returned parts of the rational. * md: max denominator value. Note that machine floating point number * has a finite resolution (10e-16 ish for 64 bit double), so specifying * a "best match with minimal error" is often wrong, because one can * always just retrieve the significand and return that divided by * 2**52, which is in a sense accurate, but generally not very useful: * 1.0/7.0 would be "2573485501354569/18014398509481984", for example. */
void rat_approx(double f, int64_t md, int64_t *num, int64_t *denom) { /* a: continued fraction coefficients. */ int64_t a, h[3] = { 0, 1, 0 }, k[3] = { 1, 0, 0 }; int64_t x, d, n = 1; int i, neg = 0;
if (md <= 1) { *denom = 1; *num = (int64_t) f; return; }
if (f < 0) { neg = 1; f = -f; }
while (f != floor(f)) { n <<= 1; f *= 2; } d = f;
/* continued fraction and check denominator each step */ for (i = 0; i < 64; i++) { a = n ? d / n : 0; if (i && !a) break;
x = d; d = n; n = x % n;
x = a; if (k[1] * a + k[0] >= md) { x = (md - k[0]) / k[1]; if (x * 2 >= a || k[1] >= md) i = 65; else break; }
h[2] = x * h[1] + h[0]; h[0] = h[1]; h[1] = h[2]; k[2] = x * k[1] + k[0]; k[0] = k[1]; k[1] = k[2]; } *denom = k[1]; *num = neg ? -h[1] : h[1]; }
int main() { int i; int64_t d, n; double f;
printf("f = %16.14f\n", f = 1.0/7); for (i = 1; i <= 20000000; i *= 16) { printf("denom <= %d: ", i); rat_approx(f, i, &n, &d); printf("%lld/%lld\n", n, d); }
printf("\nf = %16.14f\n", f = atan2(1,1) * 4); for (i = 1; i <= 20000000; i *= 16) { printf("denom <= %d: ", i); rat_approx(f, i, &n, &d); printf("%lld/%lld\n", n, d); }
return 0; }</lang>Output:<lang>f = 0.14285714285714 denom <= 1: 0/1 denom <= 16: 1/7 denom <= 256: 1/7 denom <= 4096: 1/7 denom <= 65536: 1/7 denom <= 1048576: 1/7 denom <= 16777216: 1/7
f = 3.14159265358979 denom <= 1: 3/1 denom <= 16: 22/7 denom <= 256: 355/113 denom <= 4096: 355/113 denom <= 65536: 104348/33215 denom <= 1048576: 3126535/995207 denom <= 16777216: 47627751/15160384</lang>
Haskell
Note that the decimal values of the task description are truncated in some cases.
The first map finds the simplest fractions within a given radius, because the floating-point representation is not exact. The second line shows that the numbers could be parsed into fractions at compile time if they are given the right type. The last converts the string representation of the given values directly to fractions. <lang haskell>Prelude> map (\d -> Ratio.approxRational d 0.0001) [0.9054054, 0.518518, 0.75] [67 % 74,14 % 27,3 % 4] Prelude> [0.9054054, 0.518518, 0.75] :: [Rational] [4527027 % 5000000,259259 % 500000,3 % 4] Prelude> map (fst . head . Numeric.readFloat) ["0.9054054", "0.518518", "0.75"] :: [Rational] [4527027 % 5000000,259259 % 500000,3 % 4]</lang>
J
J's x: built in will find a rational number which "best matches" a floating point number.
<lang j> x: 0.9054054 0.518518 0.75 NB. find "exact" rational representation 127424481939351r140737488355328 866492568306r1671094481399 3r4</lang>
These numbers are ratios where the integer on the left of the r is the numerator and the integer on the right of the r is the denominator.
Note that the concept of "best" has to do with the expected precision of the argument: <lang j> x: 0.9 0.5 9r10 1r2
x: 0.9054 0.5185
4527r5000 1037r2000
x: 0.9054054 0.5185185
127424481939351r140737488355328 1037037r2000000
x: 0.9054054054 0.5185185185
5358191125333r5918002138463 6073341499873r11712872893031
x: 0.9054054054054 0.5185185185185
67r74 14r27
x: 0.9054054054054054 0.5185185185185185
67r74 14r27</lang>
Note that J allows us to specify an epsilon, for the purpose of recognizing a best fit, but the allowed values must be rather small. In J version 6, the value 5e_11 was nearly the largest epsilon allowed:
<lang j> x:(!. 5e_11) 0.9054054054 0.5185185185 67r74 14r27</lang>
(Note that epsilon will be scaled by magnitude of the largest number involved in a comparison when testing floating point representations of numbers for "equality". Note also that this J implementation uses 64 bit ieee floating point numbers.)
Here are some other alternatives for dealing with decimals and fractions:
<lang j> 0j10": x:inv x: 0.9054054 0.518518 0.75 NB. invertible (shown to 10 decimal places) 0.9054054000 0.5185180000 0.7500000000
0j10": x:inv 67r74 42r81 3r4 NB. decimal representation (shown to 10 decimal places)
0.9054054054 0.5185185185 0.7500000000
x: x:inv 67r74 42r81 3r4 NB. invertible
67r74 14r27 3r4</lang>
PARI/GP
Quick and dirty. <lang parigp>convert(x)={
my(n=0); while(x-floor(x*10^n)/10^n!=0.,n++); floor(x*10^n)/10^n
};</lang>
Perl
Note: the following is considerably more complicated than what was specified, because the specification is not, well, specific. Three methods are provided with different interpretation of what "conversion" means: keeping the string representation the same, keeping machine representation the same, or find best approximation with denominator in a reasonable range. None of them takes integer overflow seriously (though the best_approx is not as badly subject to it), so not ready for real use. <lang perl>sub gcd {
my ($m, $n) = @_;
($m, $n) = ($n, $m % $n) while $n;
return $m
}
sub rat_machine {
my $n = shift;
my $denom = 1;
while ($n != int $n) {
# assuming the machine format is base 2, and multiplying
# by 2 doesn't change the mantissa
$n *= 2;
# multiply denom by 2, ignoring (very) possible overflow
$denom <<= 1;
}
if ($n) {
my $g = gcd($n, $denom);
$n /= $g;
$denom /= $g;
}
return $n, $denom;
}
- helper, make continued fraction back into normal fraction
sub get_denom {
my ($num, $denom) = (1, pop @_);
for (reverse @_) {
($num, $denom) = ($denom, $_ * $denom + $num);
}
wantarray ? ($num, $denom) : $denom
}
sub best_approx {
my ($n, $limit) = @_;
my ($denom, $neg);
if ($n < 0) {
$neg = 1;
$n = -$n;
}
my $int = int($n);
my ($num, $denom, @coef) = (1, $n - $int);
# continued fraction, sort of
while (1) {
# make sure it terminates
last if $limit * $denom < 1;
my $i = int($num / $denom);
# not the right way to get limit, but it works
push @coef, $i;
if (get_denom(@coef) > $limit) {
pop @coef;
last;
}
# we lose precision here, but c'est la vie
($num, $denom) = ($denom, $num - $i * $denom);
}
($num, $denom) = get_denom @coef;
$num += $denom * $int;
return $neg ? -$num : $num, $denom;
}
sub rat_string {
my $n = shift;
my $denom = 1;
my $neg;
# trival xyz.0000 ... case
$n =~ s/\.0+$//;
return $n, 1 unless $n =~ /\./;
if ($n =~ /^-/) {
$neg = 1;
$n =~ s/^-//;
}
# shift decimal point to the right till it's gone
$denom *= 10 while $n =~ s/\.(\d)/$1\./;
$n =~ s/\.$//;
# removing leading zeros lest it looks like octal
$n =~ s/^0*//;
if ($n) {
my $g = gcd($n, $denom);
$n /= $g;
$denom /= $g;
}
return $neg ? -$n : $n, $denom;
}
my $limit = 1e8; my $x = 3/8; print "3/8 = $x:\n"; printf "machine: %d/%d\n", rat_machine $x; printf "string: %d/%d\n", rat_string $x; printf "approx below $limit: %d/%d\n", best_approx $x, $limit;
$x = 137/4291; print "\n137/4291 = $x:\n"; printf "machine: %d/%d\n", rat_machine $x; printf "string: %d/%d\n", rat_string $x; printf "approx below $limit: %d/%d\n", best_approx $x, $limit;
$x = sqrt(1/2); print "\n1/sqrt(2) = $x\n"; printf "machine: %d/%d\n", rat_machine $x; printf "string: %d/%d\n", rat_string $x; printf "approx below 10: %d/%d\n", best_approx $x, 10; printf "approx below 100: %d/%d\n", best_approx $x, 100; printf "approx below 1000: %d/%d\n", best_approx $x, 1000; printf "approx below 10000: %d/%d\n", best_approx $x, 10000; printf "approx below 100000: %d/%d\n", best_approx $x, 100000; printf "approx below $limit: %d/%d\n", best_approx $x, $limit;
$x = -4 * atan2(1,1); print "\n-Pi = $x\n"; printf "machine: %d/%d\n", rat_machine $x; printf "string: %d/%d\n", rat_string $x;
for (map { 10 ** $_ } 1 .. 10) {
printf "approx below %g: %d / %d\n", $_, best_approx($x, $_)
}</lang>
Output:
3/8 = 0.375: machine: 3/8 string: 3/8 approx below 100000000: 3/8 137/4291 = 0.0319272896760662: machine: 2300603678209305/72057594037927936 string: 159636448380331/5000000000000000 approx below 100000000: 137/4291 1/sqrt(2) = 0.707106781186548 machine: 6369051672525773/9007199254740992 string: 176776695296637/250000000000000 approx below 10: 5/7 approx below 100: 29/41 approx below 1000: 408/577 approx below 10000: 5741/8119 approx below 100000: 33461/47321 approx below 100000000: 38613965/54608393 -Pi = -3.14159265358979 machine: -884279719003555/281474976710656 string: -314159265358979/100000000000000 approx below 10: -22 / 7 approx below 100: -22 / 7 approx below 1000: -355 / 113 approx below 10000: -355 / 113 approx below 100000: -208341 / 66317 approx below 1e+06: -1146408 / 364913 approx below 1e+07: -5419351 / 1725033 approx below 1e+08: -245850922 / 78256779 approx below 1e+09: -1881244168 / 598818617 approx below 1e+10: -9978066541 / 3176117225
Perl 6
<lang perl6>sub decimal_to_fraction ( Str $n, Int $rep_digits = 0 ) returns Str {
my ( $int, $dec ) = ( $n ~~ /^ (\d+) \. (\d+) $/ )».Str or die;
my ( $numer, $denom ) = ( $dec, 10 ** $dec.bytes );
if $rep_digits {
my $to_move = $dec.bytes - $rep_digits;
$numer -= $dec.substr(0, $to_move);
$denom -= 10 ** $to_move;
}
my $rat = Rat.new( $numer.Int, $denom.Int ).perl; return $int ?? "$int $rat" !! $rat;
}
my @a = ['0.9054', 3], ['0.518', 3], ['0.75', 0], (^4).map({['12.34567', $_]}); for @a -> [ $n, $d ] {
say "$n with $d repeating digits = ", decimal_to_fraction( $n, $d );
}</lang>
Output:
0.9054 with 3 repeating digits = 67/74 0.518 with 3 repeating digits = 14/27 0.75 with 0 repeating digits = 3/4 12.34567 with 0 repeating digits = 12 34567/100000 12.34567 with 1 repeating digits = 12 31111/90000 12.34567 with 2 repeating digits = 12 17111/49500 12.34567 with 3 repeating digits = 12 1279/3700
Python
Note that the decimal values of the task description are truncated in some cases.
The first loop limits the size of the denominator, because the floating-point representation is not exact. The second converts the string representation of the given values directly to fractions. <lang python>>>> from fractions import Fraction >>> for d in (0.9054054, 0.518518, 0.75): print(d, Fraction.from_float(d).limit_denominator(100))
0.9054054 67/74 0.518518 14/27 0.75 3/4 >>> for d in '0.9054054 0.518518 0.75'.split(): print(d, Fraction(d))
0.9054054 4527027/5000000 0.518518 259259/500000 0.75 3/4 >>> </lang>
Ruby
Note that the decimal values of the task description are truncated in some cases.
This converts the string representation of the given values directly to fractions. <lang ruby>> '0.9054054 0.518518 0.75'.split.each { |d| puts "%s %s" % [d, Rational(d)] } 0.9054054 4527027/5000000 0.518518 259259/500000 0.75 3/4 => ["0.9054054", "0.518518", "0.75"]</lang>
This loop finds the simplest fractions within a given radius, because the floating-point representation is not exact. <lang ruby>> [0.9054054, 0.518518, 0.75].each { |d| puts "%s %s" % [d, Rational(d).rationalize(0.0001)] } 0.9054054 67/74 0.518518 14/27 0.75 3/4 => [0.9054054, 0.518518, 0.75]</lang>
Tcl
Here is a complete script with the implemented function and a small test suite (which is executed when this script is called directly from a shell) - originally on http://wiki.tcl.tk/752: <lang Tcl>#!/usr/bin/env tclsh
proc dbl2frac {dbl {eps 0.000001}} {
for {set den 1} {$den<1024} {incr den} {
set num [expr {round($dbl*$den)}]
if {abs(double($num)/$den - $dbl) < $eps} break
}
list $num $den
}
- -------------------- That's all... the rest is the test suite
if {[file tail $argv0] eq [file tail [info script]]} {
foreach {test -> expected} {
{dbl2frac 0.518518} -> {42 81} {dbl2frac 0.75} -> {3 4} {dbl2frac 0.9054054} -> {67 74}
} {
catch $test res if {$res ne $expected} { puts "$test -> $res, expected $expected" }
}
}</lang> Running it shows one unexpected result, but on closer examination it is clear that 14/27 equals 42/81, so it should indeed be the right solution:
~ $ fractional.tcl dbl2frac 0.518518 -> 14 27, expected 42 81 ~ $