Convert decimal number to rational
Program to convert a decimal number to fraction.
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
- Task Description
- Write a function/routine/method/... that transform a decimal number to fraction.
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>
J
<lang j> x: 0.9054054 0.518518 0.75 NB. find "exact" rational representation 127424481939351r140737488355328 866492568306r1671094481399 3r4
0j10": x:inv x: 0.9054054 0.518518 0.75 NB. invertable (shown to 10 decimal places)
0.9054054000 0.5185180000 0.7500000000
0j10": x:inv 67r74 42r81 3r4 NB. decimal represenation (shown to 10 decimal places)
0.9054054054 0.5185185185 0.7500000000
x: x:inv 67r74 42r81 3r4 NB. invertable
67r74 14r27 3r4</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);
sub total_denom; # continued fraction, sort of for (1 .. 10) { last if $limit * $denom < 1; my $i = int($num / $denom); last if $i > $limit; push @coef, $i;
# not the right way to get limit, but it works last if get_denom(@coef) >= $limit;
# 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 = 13/291; print "\n13/291 = $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 $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 13/291 = 0.0446735395189003: machine: 6438135549780503/144115188075855872 string: 446735395189003/10000000000000000 approx below 100000000: 13/291 1/sqrt(2) = 0.707106781186548 machine: 6369051672525773/9007199254740992 string: 176776695296637/250000000000000 approx below 100000000: 2378/3363 -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: -4272943 / 1360120 approx below 1e+08: -4272943 / 1360120 approx below 1e+09: -4272943 / 1360120 approx below 1e+10: -4272943 / 1360120
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 the second uses the Decimal module to convert an accurate Decimal representation of the given values to a fraction. <lang python>>>> from fractions import Fraction >>> for d in (0.9054054, 0.518518, 0.75): print(d, Fraction(d).limit_denominator(100))
0.9054054 67/74 0.518518 14/27 0.75 3/4 >>> from decimal import Decimal >>> for d in '0.9054054 0.518518 0.75'.split(): print(d, Fraction(Decimal(d)))
0.9054054 4527027/5000000 0.518518 259259/500000 0.75 3/4 >>> </lang>