The task is to write a program to transform a decimal number into a fraction in lowest terms.
It is not always possible to do this exactly. For instance, while rational numbers can be converted to decimal representation, some of them need an infinite number of digits to be represented exactly in decimal form. Namely,repeating decimals such as 1/3 = 0.333...
Because of this, the following fractions cannot be obtained (reliably) unless the language has some way of representing repeating decimals:
Acceptable output:
Finite decimals are of course no problem:
T Rational((Int numerator, Int denominator)) F String() I .denominator == 1 R String(.numerator) E R .numerator‘//’(.denominator)F rationalize(x, tol = 1e-12) V xx = x V flagNeg = xx < 0.0 I flagNeg xx = -xx I xx < 1e-10 R Rational(0, 1) I abs(xx - round(xx)) < tol R Rational(Int(xx), 1) V a = 0 V b = 1 V c = Int(ceil(xx)) V d = 1 V aux1 = 7FFF'FFFF I/ 2 L c < aux1 & d < aux1 V aux2 = (Float(a) + Float(c)) / (Float(b) + Float(d)) I abs(xx - aux2) < tol L.break I xx > aux2 a += c b += d E c += a d += b V g = gcd(a + c, b + d) I flagNeg R Rational(-(a + c) I/ g, (b + d) I/ g) E R Rational((a + c) I/ g, (b + d) I/ g)print(rationalize(0.9054054054))print(rationalize(0.9054054054, 0.0001))print(rationalize(0.5185185185))print(rationalize(0.5185185185, 0.0001))print(rationalize(0.75))print(rationalize(0.1428571428, 0.001))print(rationalize(35.000))print(rationalize(35.001))print(rationalize(0.9))print(rationalize(0.99))print(rationalize(0.909))print(rationalize(0.909, 0.001))
1910136854//210970339167//74983902907//189752703514//273//41//73535001//10009//1099//100909//100010//11
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, ...).
generictypeRealisdigits<>;procedureReal_To_Rational(R:Real;Bound:Positive;Nominator:outInteger;Denominator:outPositive);
The implementation (just brute-force search for the best approximation with Denominator less or equal Bound):
procedureReal_To_Rational(R:Real;Bound:Positive;Nominator:outInteger;Denominator:outPositive)isError:Real;Best:Positive:=1;Best_Error:Real:=Real'Last;beginifR=0.0thenNominator:=0;Denominator:=1;return;elsifR<0.0thenReal_To_Rational(-R,Bound,Nominator,Denominator);Nominator:=-Nominator;return;elseforIin1..BoundloopError:=abs(Real(I)*R-Real'Rounding(Real(I)*R));ifError<Best_ErrorthenBest:=I;Best_Error:=Error;endif;endloop;endif;Denominator:=Best;Nominator:=Integer(Real'Rounding(Real(Denominator)*R));endReal_To_Rational;
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:
withAda.Text_IO;WithReal_To_Rational;procedureConvert_Decimal_To_RationalistypeMy_RealisnewLong_Float;-- change this for another "Real" typepackageFIOis newAda.Text_IO.Float_IO(My_Real);procedureR2RisnewReal_To_Rational(My_Real);Nom,Denom:Integer;R:My_Real;beginloopAda.Text_IO.New_Line;FIO.Get(R);FIO.Put(R,Fore=>2,Aft=>9,Exp=>0);exitwhenR=0.0;forIin0..4loopR2R(R,10**I,Nom,Denom);Ada.Text_IO.Put(" "&Integer'Image(Nom)&" /"&Integer'Image(Denom));endloop;endloop;endConvert_Decimal_To_Rational;
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 / 296031.415926536 31 / 1 157 / 5 377 / 12 3550 / 113 208696 / 6643 0.000000000
--------- RATIONAL APPROXIMATION TO DECIMAL NUMBER --------- approxRatio :: Real -> Real -> RatioonapproxRatio(epsilon,n)if{real,integer}contains(classofepsilon)and0<epsilonthen-- Givensetetoepsilonelse-- Defaultseteto1/10000endifscriptgcdeon|λ|(e,x,y)script_gcdon|λ|(a,b)ifb<ethenaelse|λ|(b,amodb)endifend|λ|endscript|λ|(abs(x),abs(y))of_gcdend|λ|endscriptsetcto|λ|(e,1,n)ofgcdeRatio((ndivc),(1divc))endapproxRatio-- Ratio :: Int -> Int -> RatioonRatio(n,d){type:"Ratio",n:n,d:d}endRatio-- showRatio :: Ratio -> StringonshowRatio(r)(nofrasstring)&"/"&(dofrasstring)endshowRatio--------------------------- TEST -------------------------onrunscriptratioString-- Using a tolerance epsilon of 1/10000on|λ|(x)(xasstring)&" -> "&showRatio(approxRatio(1.0E-4,x))end|λ|endscriptunlines(map(ratioString,¬{0.9054054,0.518518,0.75}))-- 0.9054054 -> 67/74-- 0.518518 -> 14/27-- 0.75 -> 3/4endrun-------------------- GENERIC FUNCTIONS --------------------- abs :: Num -> Numonabs(x)if0>xthen-xelsexendifendabs-- Lift 2nd class handler function into 1st class script wrapper-- mReturn :: First-class m => (a -> b) -> m (a -> b)onmReturn(f)ifclassoffisscriptthenfelsescriptproperty|λ|:fendscriptendifendmReturn-- map :: (a -> b) -> [a] -> [b]onmap(f,xs)tellmReturn(f)setlngtolengthofxssetlstto{}repeatwithifrom1tolngsetendoflstto|λ|(itemiofxs,i,xs)endrepeatreturnlstendtellendmap-- unlines :: [String] -> Stringonunlines(xs)-- A single string formed by the intercalation-- of a list of strings with the newline character.set{dlm,mytext item delimiters}to¬{mytext item delimiters,linefeed}setstoxsastextsetmytext item delimiterstodlmsendunlines
0.9054054 -> 67/740.518518 -> 14/270.75 -> 3/4
Array:=[]inputbox,string,EnterNumberstringsplit,string,string,.if(string1=0)string1=loop,parse,string,.ifA_index=2loop,parse,A_loopfieldArray[A_index]:=A_loopfield,k:=A_indexif(k=1){numerator:=Array[1]Denominator:=10gotolabel}Original1:=KTo_rn:=floor(k/2)M_M:=k-To_rnOriginal2:=k-To_rnloop{loop,%To_rn{Check1.=Array[k]Check2.=Array[M_M]k--m_M--}if(check1=check2){ ;~ process beginsTO check;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;loop,%To_rnnines.=9loop,%k-TO_rnZeroes.=0loop%k-TO_rnMinus.=Array[A_index]loop%kPlus.=Array[A_index]if(minus="")minus:=0Numerator:=Plus-minusDenominator:=Nines.Zeroes ;;;;;;;;;;;;;HCFgoto,label}Check1=check2=k:=Original1m_M:=original2+A_indexTO_rn--if(to_rn=0){zeroes=loop%original1zeroes.=0Denominator:=1.zeroesnumerator:=string2goto,label}}esc::Exitapplabel:Index:=2loop{if(mod(denominator,numerator)=0)HCF:=numeratorif(index=floor(numerator/2))breakif(mod(numerator,index)=0)&&(mod(denominator,index)=0){HCF=%index%index++}elseindex++}if(HCF="")Ans:=numerator"/"DenominatorelseAns:=floor(numerator/HCF)"/"floor(Denominator/HCF)MsgBox%String." -> ".String1." ".Ansreload
0.9054054 -> 67/740.518518 -> 14/270.75 -> 3/4
( ( exact = integerPart decimalPart z . @(!arg:?integerPart "." ?decimalPart) & !integerPart + ( @( !decimalPart : (? ((%@:~0) ?:?decimalPart)) [?z ) & !decimalPart*10^(-1*!z) | 0 ) | !arg )& ( approximation = integerPart firstDecimals repeatingDecimals , x y z z-y x-y numerator denominator . @( !arg : ?integerPart "." [?x ?firstDecimals ?repeatingDecimals [?y !repeatingDecimals [?z ) & !z+-1*!y:?z-y & !x+-1*!y:?x-y & 10:?numerator:?denominator & ( !z-y:0&0:?repeatingDecimals | 9:?denominator & whl ' ( !z+-1:>!y:?z & !numerator*10:?numerator & !denominator*10+9:?denominator ) & @(!repeatingDecimals:? #?repeatingDecimals) ) & ( @(!firstDecimals:? #?firstDecimals) | 0:?firstDecimals ) & !integerPart + !firstDecimals*10^(!x-y+!z-y) + !numerator*!denominator^-1*!repeatingDecimals*10^!x-y )& "0.9054054054" "0.5185185185" "0.75" "0.905405400" "0.1428571428" "35.000" "35.001" "0.00000000001" "0.000001000001" "0.9" "0.99" "0.909" "0.9090" "0.90909" : ?decs& whl ' ( !decs:%?dec ?decs & approximation$!dec:?approx & out $ ( !dec "=" (exact$!dec:?precise) ( !approx:!precise& | str$("(approx. " !approx ")") ) ) ));Output:
0.9054054054 = 4527027027/5000000000 (approx. 67/74)0.5185185185 = 1037037037/2000000000 (approx. 14/27)0.75 = 3/40.905405400 = 4527027/50000000.1428571428 = 357142857/250000000035.000 = 3535.001 = 35001/10000.00000000001 = 1/1000000000000.000001000001 = 1000001/1000000000000 (approx. 1/999999)0.9 = 9/100.99 = 99/100 (approx. 1)0.909 = 909/10000.9090 = 909/1000 (approx. 10/11)0.90909 = 90909/100000 (approx. 10/11)
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.
#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. */voidrat_approx(doublef,int64_tmd,int64_t*num,int64_t*denom){/* a: continued fraction coefficients. */int64_ta,h[3]={0,1,0},k[3]={1,0,0};int64_tx,d,n=1;inti,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;elsebreak;}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];}intmain(){inti;int64_td,n;doublef;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);}return0;}
Output:
f = 0.14285714285714denom <= 1: 0/1denom <= 16: 1/7denom <= 256: 1/7denom <= 4096: 1/7denom <= 65536: 1/7denom <= 1048576: 1/7denom <= 16777216: 1/7f = 3.14159265358979denom <= 1: 3/1denom <= 16: 22/7denom <= 256: 355/113denom <= 4096: 355/113denom <= 65536: 104348/33215denom <= 1048576: 3126535/995207denom <= 16777216: 47627751/15160384
usingSystem;usingSystem.Text;namespaceRosettaDecimalToFraction{publicclassFraction{publicInt64Numerator;publicInt64Denominator;publicFraction(doublef,Int64MaximumDenominator=4096){/* Translated from the C version. *//* a: continued fraction coefficients. */Int64a;varh=newInt64[3]{0,1,0};vark=newInt64[3]{1,0,0};Int64x,d,n=1;inti,neg=0;if(MaximumDenominator<=1){Denominator=1;Numerator=(Int64)f;return;}if(f<0){neg=1;f=-f;}while(f!=Math.Floor(f)){n<<=1;f*=2;}d=(Int64)f;/* continued fraction and check denominator each step */for(i=0;i<64;i++){a=(n!=0)?d/n:0;if((i!=0)&&(a==0))break;x=d;d=n;n=x%n;x=a;if(k[1]*a+k[0]>=MaximumDenominator){x=(MaximumDenominator-k[0])/k[1];if(x*2>=a||k[1]>=MaximumDenominator)i=65;elsebreak;}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];}Denominator=k[1];Numerator=neg!=0?-h[1]:h[1];}publicoverridestringToString(){returnstring.Format("{0} / {1}",Numerator,Denominator);}}classProgram{staticvoidMain(string[]args){Console.OutputEncoding=UTF8Encoding.UTF8;foreach(doubledinnewdouble[]{0.9054054,0.518518,0.75,0.4285714,0.833333,0.90909,3.14159265358979,2.7182818284590451}){varf=newFraction(d,d>=2?65536:4096);Console.WriteLine("{0,20} → {1}",d,f);}}}}
0.9054054 → 67 / 74 0.518518 → 14 / 27 0.75 → 3 / 4 0.4285714 → 3 / 7 0.833333 → 5 / 6 0.90909 → 10 / 11 3.14159265358979 → 104348 / 33215 2.71828182845905 → 49171 / 18089
#include<cmath>#include<cstdint>#include<iostream>#include<limits>#include<numeric>#include<vector>classRational{public:Rational(constint64_t&numer,constuint64_t&denom):numerator(numer),denominator(denom){}Rationalnegate(){returnRational(-numerator,denominator);}std::stringto_string(){returnstd::to_string(numerator)+" / "+std::to_string(denominator);}private:int64_tnumerator;uint64_tdenominator;};/** * Return a Rational such that its numerator / denominator = 'decimal', correct to dp decimal places, * where dp is minimum of 'decimal_places' and the number of decimal places in 'decimal'. */Rationaldecimal_to_rational(doubledecimal,constuint32_t&decimal_places){constdoubleepsilon=1.0/std::pow(10,decimal_places);constboolnegative=(decimal<0.0);if(negative){decimal=-decimal;}if(decimal<std::numeric_limits<double>::min()){returnRational(0,1);}if(std::abs(decimal-std::round(decimal))<epsilon){returnRational(std::round(decimal),1);}uint64_ta=0;uint64_tb=1;uint64_tc=static_cast<uint64_t>(std::ceil(decimal));uint64_td=1;constuint64_tauxiliary_1=std::numeric_limits<uint64_t>::max()/2;while(c<auxiliary_1&&d<auxiliary_1){constdoubleauxiliary_2=static_cast<double>(a+c)/(b+d);if(std::abs(decimal-auxiliary_2)<epsilon){break;}if(decimal>auxiliary_2){a=a+c;b=b+d;}else{c=a+c;d=b+d;}}constuint64_tdivisor=std::gcd((a+c),(b+d));Rationalresult((a+c)/divisor,(b+d)/divisor);return(negative)?result.negate():result;}intmain(){for(constdouble&decimal:{3.1415926535,0.518518,-0.75,0.518518518518,-0.9054054054054,-0.0,2.0}){std::cout<<decimal_to_rational(decimal,9).to_string()<<std::endl;}}
104348 / 3321536975 / 71309-3 / 414 / 27-67 / 740 / 12 / 1
user=> (rationalize 0.1)1/10user=> (rationalize 0.9054054)4527027/5000000user=> (rationalize 0.518518)259259/500000user=> (rationalize Math/PI)3141592653589793/1000000000000000
There are two functions for converting decimals to rationals:rational returns a rational that is mathematically equal in value to the decimal andrationalize returns a rational that approximates the decimal to the accuracy of the underlying floating-point representation.
> (rational 0.9054054)7595091/8388608> (rationalize 0.9054054)67/74> (= (rational 0.9054054) 0.9054054)T> (= (rationalize 0.9054054) 0.9054054)NIL> (rational .518518)1087411/2097152> (rationalize .518518)33279/64181> (rational .5185185)8699297/16777216> (rationalize .5185185)14/27> (rational .75)3/4> (rationalize .75)3/4
importstd.stdio,std.math,std.string,std.typecons;aliasFraction=Tuple!(int,"nominator",uint,"denominator");Fractionreal2Rational(inrealr,inuintbound)/*pure*/nothrow{if(r==0.0){returnFraction(0,1);}elseif(r<0.0){autoresult=real2Rational(-r,bound);result.nominator=-result.nominator;returnresult;}else{uintbest=1;realbestError=real.max;foreach(i;1..bound+1){// round is not pure.immutablerealerror=abs(i*r-round(i*r));if(error<bestError){best=i;bestError=error;}}returnFraction(cast(int)round(best*r),best);}}voidmain(){immutabletests=[0.750000000,0.518518000,0.905405400,0.142857143,3.141592654,2.718281828,-0.423310825,31.415926536];foreach(r;tests){writef("%8.9f ",r);foreach(i;0..5)writef(" %d/%d",real2Rational(r,10^^i).tupleof);writeln();}}
0.750000000 1/1 3/4 3/4 3/4 3/4 3/40.518518000 1/1 1/2 14/27 14/27 14/27 37031/714170.905405400 1/1 9/10 67/74 67/74 67/74 67/740.142857143 0/1 1/7 1/7 1/7 1/7 1/73.141592654 3/1 22/7 22/7 355/113 355/113 104348/332152.718281828 3/1 19/7 193/71 1457/536 25946/9545 222630/81901-0.423310825 0/1 -3/7 -11/26 -69/163 -1253/2960 -10093/2384331.415926536 31/1 157/5 377/12 3550/113 208696/6643 2918194/92889
Thanks Rudy Velthuis for Velthuis.BigRationals and Velthuis.BigDecimals library[1].
programConvert_decimal_number_to_rational;{$APPTYPE CONSOLE}usesVelthuis.BigRationals,Velthuis.BigDecimals;constTests:TArray<string>=['0.9054054','0.518518','0.75'];varRational:BigRational;Decimal:BigDecimal;beginforvartestinTestsdobeginDecimal:=test;Rational:=Decimal;Writeln(test,' = ',Rational.ToString);end;Readln;end.
maxd = 10000000#func$ rataprox f . if f < 0 neg = 1 f = -f . n = 1 while f <> floor f n = n * 2 f = f * 2 . d = f h1 = 1 k0 = 1 for i = 0 to 63 a = 0 if n <> 0 : a = d div n if i > 0 and a = 0 : break 1 x = d d = n n = x mod n x = a if k1 * a + k0 >= maxd x = (maxd - k0) div k1 if x * 2 >= a or k1 >= maxd i = 65 else break 1 . . h2 = x * h1 + h0 h0 = h1 h1 = h2 k2 = x * k1 + k0 k0 = k1 k1 = k2 . num = h1 denom = k1 if neg = 1 : num = -num return num & "/" & denom.print rataprox 0.9054054054print rataprox 0.5185185185print rataprox 0.75print rataprox 0.33333333333print rataprox 0.88888888888
67/7414/273/41/38/9
Therationalize function uses a Stern-Brocot tree[2] to find the best rational approximation of an inexact (floating point) number, for a given precision. Theinexact->exact function returns a rational approximation for the default precision 0.0001 .
(exact->inexact67/74)→0.9054054054054054(inexact->exact0.9054054054054054)→67/74(rationalize0.7978723404255319)→75/94;; finding rational approximations of PI(for((ε(in-range-1-15-1)))(writeln(format"precision:10^%d %t PI = %d"ε(rationalizePI(expt10e)))))"precision:10^-1 PI = 16/5""precision:10^-2 PI = 22/7";;🎩"precision:10^-3 PI = 201/64""precision:10^-4 PI = 333/106""precision:10^-5 PI = 355/113";; 🎩 🎩"precision:10^-6 PI = 355/113""precision:10^-7 PI = 75948/24175""precision:10^-8 PI = 100798/32085""precision:10^-9 PI = 103993/33102""precision:10^-10 PI = 312689/99532""precision:10^-11 PI = 833719/265381""precision:10^-12 PI = 4272943/1360120""precision:10^-13 PI = 5419351/1725033""precision:10^-14 PI = 58466453/18610450"
USING:kernelmath.floating-pointprettyprint;0.9054054 0.518518 0.75[double>ratio.]tri@
4077583422059235/45035996273704962335197471584895/45035996273704963/4
Fermat does this automatically.
>3.14 157 / 50; or 3.1400000000000000000000000000000000000000>10.00000 10>77.7777 777777 / 10000; or 77.7777000000000000000000000000000000000000>-5.5 -11 / 2; or -5.5000000000000000000000000000000000000000
\ Brute force search, optimized to search only within integer bounds surrounding target\ Forth 200x compliant:RealToRational( float_target int_denominator_limit -- numerator denominator ){:f:therealdenlimit|realscalenumtordenomneg?f:besterrorf:temperror:}0tonumtor0todenom9999999etobesterror\ very large error that will surely be improved upontherealF0<toneg?\ save sign for latertherealFABStotherealtherealFTRUNCf>s1+torealscale\ realscale helps set integer bounds around targetdenlimit1+1?DO\ search through possible denominators ( 1 to denlimit)Irealscale*Irealscale1-*?DO\ search within integer limits bounding the realIs>fJs>fF/\ e.g. for 3.1419e search only between 3 and 4therealF-FABStotemperrortemperrorbesterrorF<IFtemperrortobesterrorItonumtorJtodenomTHENLOOPLOOPneg?IFnumtorNEGATEtonumtorTHENnumtordenom;(run)1.618033988e100RealToRationalswap..144893.14159e1000RealToRationalswap..3551132.71828e1000RealToRationalswap..12644650.9054054e100RealToRationalswap..6774
This version doesn't require local variables, since it uses the data stack and a (separate) floating point stack.MAX-N represents the largest (positive) integer.
:RealToRational( f n1 -- n2 n3)0duprotmax-ns>ffswapfdupf0<>rfabsfdupftruncf>s1+swap( den num lim real R: neg F: best real)\ helps set integer bounds around target1+1?do\ search through possible denominatorsdupi*over1-i*?do\ search within integer limits bounding the realfoverfoveris>fjs>ff/f-fabsfdupfrotf<ifnipnipjirotfswapfrotthenfdroploop\ e.g. for 3.1419e search only between 3 and 4loopfdropfdropdropr>ifnegatethenswap;
This sort of calculation works best in base ten and with an input scheme that recognises a protocol for specifying that the decimal value has a recurring sequence, whereupon the methods taught in school could be employed. Such a protocol often conflicts with presenting a digit sequence with the last digit correctly rounded. Although many early computers worked in base ten, these days a binary base is usual, be it 2, 4, 8, or 16. Alas, five is not a factor of two nor any of its powers, and many decimal fractions, even a brief one such as 0·1, convert to a recurring sequence in binary so for example, 10·15 is in binary 1010·0010011001100110011... However, 203/20 when evaluated in binary floating-point will generate the same binary sequence as 10·15, granted that the compiler does its arithmetic correctly. Nevertheless, such a decimal value isnot the value that a binary computer will work with, except for restricted fractions such as 0·5, 0·25, 0·75, and so forth up to the precision of the arithmetic.
Rather than engage in fancy schemes, here are two "brute force" methods. The first simply multiplies the value by a large power of ten, then casts out common factors in P/Q = x*1000000000/100000000. But if the best value for Q involves factors other than two and five, this won't work well. The second method is to jiggle either P or Q upwards depending on whether P/Q is smaller or larger than X, reporting improvements as it goes. Once beyond small numbers there are many small improvements to be found, so only those much better than the previous best are reported. Loosely speaking, the number of digits correct in good values of P/Q should be the sum of the number of digits in P and Q, and more still for happy fits, but a factor of eight suffices to suppress the rabble. Thus for Pi, the famous 22/7 and 355/113 appear as desired. Later pairs use lots more digits without a surprise hit, except for the short decimal sequence which comes out as 314159/100000 that reconstitutes the given decimal fraction exactly. Which is not a good approximation for Pi, and its pairs diverge from those of the more accurate value. In other words, one must assess the precision of the given value and not be distracted by the spurious precision offered by the larger P/Q pairs, so for 3·14159 with six digits, there is little point in going further than 355/113 - with their six digits. Contrariwise, if a P/Q with few digits matches many more digits of the given number, then a source rational number can be suspected. But if given just a few digits, such as 0·518 (or 0·519, when rounded), 13/25 could be just as likely a source number as 14/27 which is further away.
The source uses the MODULE facility of F90 merely to avoid the annoyance of having to declare the type of integer function GCD. The T ("tab") format code is employed to facilitate the alignment of output, given that P/Q is presented with I0 format so that there are no spaces (as in " 22/ 7" for example), the latter being standard in F90 but an extension in earlier Fortrans.
MODULEPQ!Plays with some integer arithmetic.INTEGERMSG!Output unit number.CONTAINS!One good routine.INTEGERFUNCTIONGCD(I,J)!Greatest common divisor.INTEGERI,J!Of these two integers.INTEGERN,M,R!Workers.N=MAX(I,J)!Since I don't want to damage I or J,M=MIN(I,J)!These copies might as well be the right way around.1R=MOD(N,M)!Divide N by M to get the remainder R.IF(R.GT.0)THEN!Remainder zero?N=M!No. Descend a level.M=R!M-multiplicity has been removed from N.IF(R.GT.1)GOTO1!No point dividing by one.END IF!If R = 0, M divides N.GCD=M!There we are.END FUNCTIONGCD!Euclid lives on!SUBROUTINERATIONAL10(X)!By contrast, this is rather crude.DOUBLE PRECISIONX!The number.DOUBLE PRECISIONR!Its latest rational approach.INTEGERP,Q!For R = P/Q.INTEGERF,WHACK!Assistants.PARAMETER(WHACK=10**8)!The rescale...P=X*WHACK+0.5!Multiply by WHACK/WHACK = 1 and round to integer.Q=WHACK!Thus compute X/1, sortof.F=GCD(P,Q)!Perhaps there is a common factor.P=P/F!Divide it out.Q=Q/F!For a proper rational number.R=DBLE(P)/DBLE(Q)!So, where did we end up?WRITE(MSG,1)P,Q,X-R,WHACK!Details.1FORMAT("x - ",I0,"/",I0,T28," = ",F18.14,1" via multiplication by ",I0)END SUBROUTINERATIONAL10!Enough of this.SUBROUTINERATIONAL(X)!Use brute force in a different way.DOUBLE PRECISIONX!The number.DOUBLE PRECISIONR,E,BEST!Assistants.INTEGERP,Q!For R = P/Q.INTEGERTRY,F!Floundering.P=1+X!Prevent P = 0.Q=1!So, X/1, sortof.BEST=X*6!A largeish value for the first try.DOTRY=1,10000000!Pound away.R=DBLE(P)/DBLE(Q)!The current approximation.E=X-R!Deviation.IF(ABS(E).LE.BEST)THEN!Significantly better than before?BEST=ABS(E)*0.125!Yes. Demand eightfold improvement to notice.F=GCD(P,Q)!We may land on a multiple.IF(BEST.LT.0.1D0)WRITE(MSG,1)P/F,Q/F,E!Skip early floundering.1FORMAT("x - ",I0,"/",I0,T28," = ",F18.14)!Try to align columns.IF(F.NE.1)WRITE(MSG,*)"Common factor!",F!A surprise!IF(E.EQ.0)EXIT!Perhaps we landed a direct hit?END IF!So much for possible announcements.IF(E.GT.0)THEN!Is R too small?P=P+CEILING(E*Q)!Yes. Make P bigger by the shortfall.ELSE IF(E.LT.0)THEN!But perhaps R is too big?Q=Q+1!If so, use a smaller interval.END IF!So much for adjustments.END DO!Try again.END SUBROUTINERATIONAL!Limited integers, limited sense.SUBROUTINERATIONALISE(X,WOT)!Run the tests.DOUBLE PRECISIONX!The value.CHARACTER*(*)WOT!Some blather.WRITE(MSG,*)X,WOT!Explanations can help.CALLRATIONAL10(X)!Try a crude method.CALLRATIONAL(X)!Try a laborious method.WRITE(MSG,*)!Space off.END SUBROUTINERATIONALISE!That wasn't much fun.END MODULEPQ!But computer time is cheap.PROGRAMAPPROXUSEPQDOUBLE PRECISIONPI,EMSG=6WRITE(MSG,*)"Rational numbers near to decimal values."WRITE(MSG,*)PI=1!Thus get a double precision conatant.PI=4*ATAN(PI)!That will determine the precision of ATAN.E=DEXP(1.0D0)!Rather than blabber on about 1 in double precision.CALLRATIONALISE(0.1D0,"1/10 Repeating in binary..")CALLRATIONALISE(3.14159D0,"Pi approx.")CALLRATIONALISE(PI,"Pi approximated better.")CALLRATIONALISE(E,"e: rational approximations aren't much use.")CALLRATIONALISE(10.15D0,"Exact in decimal, recurring in binary.")WRITE(MSG,*)WRITE(MSG,*)"Variations on 67/74"CALLRATIONALISE(0.9054D0,"67/74 = 0·9(054) repeating in base 10")CALLRATIONALISE(0.9054054D0,"Two repeats.")CALLRATIONALISE(0.9054054054D0,"Three repeats.")WRITE(MSG,*)WRITE(MSG,*)"Variations on 14/27"CALLRATIONALISE(0.518D0,"14/27 = 0·(518) repeating in decimal.")CALLRATIONALISE(0.519D0,"Rounded.")CALLRATIONALISE(0.518518D0,"Two repeats, truncated.")CALLRATIONALISE(0.518519D0,"Two repeats, rounded.")END
Some examples. Each rational value is followed by X - P/Q. Notice that 0·(518) repeating, presented as 0·518518, isnot correctly rounded.
Rational numbers near to decimal values. 0.100000000000000 1/10 Repeating in binary..x - 1/10 = 0.00000000000000 via multiplication by 100000000x - 1/2 = -0.40000000000000x - 1/7 = -0.04285714285714x - 1/10 = 0.00000000000000 3.14159000000000 Pi approx.x - 314159/100000 = 0.00000000000000 via multiplication by 100000000x - 16/5 = -0.05841000000000x - 22/7 = -0.00126714285714x - 355/113 = -0.00000292035398x - 9563/3044 = -0.00000001314060x - 85712/27283 = -0.00000000109959x - 238010/75761 = -0.00000000013199x - 314159/100000 = 0.00000000000000 3.14159265358979 Pi approximated better.x - 62831853/20000000 = 0.00000000358979 via multiplication by 100000000x - 16/5 = -0.05840734641021x - 22/7 = -0.00126448926735x - 355/113 = -0.00000026676419x - 104348/33215 = -0.00000000033163x - 312689/99532 = -0.00000000002914x - 1146408/364913 = -0.00000000000161x - 5419351/1725033 = -0.00000000000002 2.71828182845905 e: rational approximations aren't much use.x - 271828183/100000000 = -0.00000000154095 via multiplication by 100000000x - 3/1 = -0.28171817154095x - 11/4 = -0.03171817154095x - 49/18 = -0.00394039376318x - 87/32 = -0.00046817154095x - 193/71 = -0.00002803069588x - 1457/536 = -0.00000175363051x - 9620/3539 = -0.00000017210609x - 23225/8544 = -0.00000000674695x - 49171/18089 = -0.00000000027665x - 566827/208524 = -0.00000000001154x - 3820276/1405401 = -0.00000000000130x - 11411657/4198114 = -0.00000000000012 10.1500000000000 Exact in decimal, recurring in binary.x - 203/20 = 0.00000000000000 via multiplication by 100000000x - 41/4 = -0.10000000000000x - 132/13 = -0.00384615384615x - 203/20 = 0.00000000000000 Variations on 67/74 0.905400000000000 67/74 = 0·9(054) repeating in base 10x - 4527/5000 = 0.00000000000000 via multiplication by 100000000x - 1/1 = -0.09460000000000x - 9/10 = 0.00540000000000x - 19/21 = 0.00063809523810x - 67/74 = -0.00000540540541x - 2029/2241 = 0.00000062472111x - 4527/5000 = 0.00000000000000 0.905405400000000 Two repeats.x - 4527027/5000000 = 0.00000000000000 via multiplication by 100000000x - 1/1 = -0.09459460000000x - 9/10 = 0.00540540000000x - 19/21 = 0.00064349523810x - 67/74 = -0.00000000540541x - 2012029/2222241 = 0.00000000067562x - 2228707/2461557 = 0.00000000008442x - 2259125/2495153 = 0.00000000001050x - 2263011/2499445 = 0.00000000000120x - 2263480/2499963 = 0.00000000000008x - 4527027/5000000 = 0.00000000000000 0.905405405400000 Three repeats.x - 90540541/100000000 = -0.00000000460000 via multiplication by 100000000x - 1/1 = -0.09459459460000x - 9/10 = 0.00540540540000x - 19/21 = 0.00064350063810x - 67/74 = -0.00000000000541 Variations on 14/27 0.518000000000000 14/27 = 0·(518) repeating in decimal.x - 259/500 = 0.00000000000000 via multiplication by 100000000x - 1/1 = -0.48200000000000x - 1/2 = 0.01800000000000x - 13/25 = -0.00200000000000x - 29/56 = 0.00014285714286x - 72/139 = 0.00001438848921x - 259/500 = 0.00000000000000 0.519000000000000 Rounded.x - 519/1000 = 0.00000000000000 via multiplication by 100000000x - 1/1 = -0.48100000000000x - 1/2 = 0.01900000000000x - 13/25 = -0.00100000000000x - 41/79 = 0.00001265822785x - 478/921 = -0.00000108577633x - 519/1000 = 0.00000000000000 0.518518000000000 Two repeats, truncated.x - 259259/500000 = 0.00000000000000 via multiplication by 100000000x - 1/1 = -0.48148200000000x - 1/2 = 0.01851800000000x - 13/25 = -0.00148200000000x - 14/27 = -0.00000051851852x - 32929/63506 = 0.00000006468680x - 36471/70337 = 0.00000000804697x - 36975/71309 = 0.00000000086946x - 37031/71417 = 0.00000000008401x - 185183/357139 = 0.00000000000560x - 259259/500000 = 0.00000000000000 0.518519000000000 Two repeats, rounded.x - 518519/1000000 = 0.00000000000000 via multiplication by 100000000x - 1/1 = -0.48148100000000x - 1/2 = 0.01851900000000x - 13/25 = -0.00148100000000x - 14/27 = 0.00000048148148x - 35461/68389 = -0.00000006008276x - 39283/75760 = -0.00000000739176x - 39815/76786 = -0.00000000085953x - 39885/76921 = -0.00000000001300x - 478634/923079 = 0.00000000000108x - 518519/1000000 = 0.00000000000000
'' Written in FreeBASIC'' (no error checking, limited to 64-bit signed math)typenumberaslongint#definestr2numvallng#definepow10(n)clngint(10^(n))functiongcd(aasnumber,basnumber)asnumberifa=0thenreturnbreturngcd(bmoda,a)endfunctionfunctionparserational(nasconststring)asstringdimasstringwhole,dec,num,denomdimasnumberiwhole,idec,inum,idenom,igcd'' find positions of '.', '(' and ')' in codedimasintegerdpos,r1pos,r2posdpos=instr(n&".",".")r1pos=instr(n&"(","(")r2pos=instr(n&")",")")'' extract sections of number (whole, decimal, repeated numerator), generate '999' denominatorwhole=left(n,dpos-1)dec=mid(n,dpos+1,r1pos-dpos-1)num=mid(n,r1pos+1,r2pos-r1pos-1)denom=string(len(num),"9"):ifdenom=""thendenom="1"'' parse sections to integeriwhole=str2num(whole)idec=str2num(dec)inum=str2num(num)idenom=str2num(denom)'' if whole was negative, decimal and repeated sections need to be negative tooifleft(ltrim(whole),1)="-"thenidec=-idec:inum=-inum'' add decimal part to repeated fraction, and scale downinum+=idec*idenomidenom*=pow10(len(dec))'' add integer part to fractioninum+=iwhole*idenom'' simplify fractionigcd=abs(gcd(inum,idenom))ifigcd<>0theninum\=igcdidenom\=igcdendifreturninum&" / "&idenom&" = "&(inum/idenom)endfunctiondata"0.9(054)","0.(518)","-.12(345)",""dodimasstringnreadnifn=""thenexitdoprintn&":",parserational(n)loop
println[toRational[0.9054054]]println[toRational[0.518518]]println[toRational[0.75]]
4527027/5000000 (exactly 0.9054054)259259/500000 (exactly 0.518518)3/4 (exactly 0.75)
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.
Programs in Fōrmulæ are created/edited online in itswebsite.
Inthis page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.
Solution
The FōrmulæRationalize expression converts from decimal numberts to rational in lower terms.
FōrmulæRationalize expression can convert from decimal numbers with infinite number of repeating digits. The second arguments specifies the number of repeating digits.
In the following example, a conversion of the resulting rational back to decimal is provided in order to prove that it was correct:
Even when rationalization expressions are intrinsic in Fōrmulæ, we can write explicit functions:
Go has no native decimal representation so strings are used as input here. The program parses it into a Go rational number, which automatically reduces.
packagemainimport("fmt""math/big")funcmain(){for_,d:=range[]string{"0.9054054","0.518518","0.75"}{ifr,ok:=new(big.Rat).SetString(d);ok{fmt.Println(d,"=",r)}else{fmt.Println(d,"invalid decimal number")}}}
Output:
0.9054054 = 4527027/50000000.518518 = 259259/5000000.75 = 3/4
Solution:
Uses theRational number class andRationalCategory helper class created in the solution to theArithmetic/Rational task.
Test:
Number.metaClass.mixinRationalCategory[0.9054054,0.518518,0.75,Math.E,-0.423310825,Math.PI,0.111111111111111111111111].each{printf"%30.27f %s\n",it,itasRational}
Output:
0.905405400000000000000000000 4527027//5000000 0.518518000000000000000000000 259259//500000 0.750000000000000000000000000 3//4 2.718281828459045000000000000 6121026514868073//2251799813685248-0.423310825000000000000000000 -16932433//40000000 3.141592653589793000000000000 884279719003555//281474976710656 0.111111111111111111111111000 111111111111111111111111//1000000000000000000000000
Clearly this solution does not make any assumptions or approximations regarding repeating decimals.
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.
Prelude>map(\d->Ratio.approxRationald0.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]
J'sx: built-in will find a rational number which "best matches" a floating point number.
x:0.90540540.5185180.75NB. find "exact" rational representation127424481939351r140737488355328866492568306r16710944813993r4
These numbers are ratios where the integer on the left of ther is the numerator and the integer on the right of ther is the denominator. (Note that this use is in analogy with floating point notion, though it is true that hexadecimal notation and some languages' typed numeric notations use letters within numbers. Using letters rather than other characters makes lexical analysis simpler to remember - both letters and numbers are almost always "word forming characters".)
Note that the concept of "best" has to do with the expected precision of the argument:
x:0.90.59r101r2x:0.90540.51854527r50001037r2000x:0.90540540.5185185127424481939351r1407374883553281037037r2000000x:0.90540540540.51851851855358191125333r59180021384636073341499873r11712872893031x:0.90540540540540.518518518518567r7414r27x:0.90540540540540540.518518518518518567r7414r27
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:
x:(!.5e_11)0.90540540540.518518518567r7414r27
(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:
0j10":x:invx:0.90540540.5185180.75NB. invertible (shown to 10 decimal places)0.90540540000.51851800000.75000000000j10":x:inv67r7442r813r4NB. decimal representation (shown to 10 decimal places)0.90540540540.51851851850.7500000000x:x:inv67r7442r813r4NB. invertible67r7414r273r4
doublefractionToDecimal(Stringstring){intindexOf=string.indexOf(' ');intinteger=0;intnumerator,denominator;if(indexOf!=-1){integer=Integer.parseInt(string.substring(0,indexOf));string=string.substring(indexOf+1);}indexOf=string.indexOf('/');numerator=Integer.parseInt(string.substring(0,indexOf));denominator=Integer.parseInt(string.substring(indexOf+1));returninteger+((double)numerator/denominator);}StringdecimalToFraction(doublevalue){Stringstring=String.valueOf(value);string=string.substring(string.indexOf('.')+1);intnumerator=Integer.parseInt(string);intdenominator=(int)Math.pow(10,string.length());intgcf=gcf(numerator,denominator);if(gcf!=0){numerator/=gcf;denominator/=gcf;}intinteger=(int)value;if(integer!=0)return"%d %d/%d".formatted(integer,numerator,denominator);return"%d/%d".formatted(numerator,denominator);}intgcf(intvalueA,intvalueB){if(valueB==0)returnvalueA;elsereturngcf(valueB,valueA%valueB);}
67/74 = 0.905405405405405414/27 = 0.51851851851851850.9054054 = 4527027/50000000.518518 = 259259/500000
importorg.apache.commons.math3.fraction.BigFraction;publicclassTest{publicstaticvoidmain(String[]args){double[]n={0.750000000,0.518518000,0.905405400,0.142857143,3.141592654,2.718281828,-0.423310825,31.415926536};for(doubled:n)System.out.printf("%-12s : %s%n",d,newBigFraction(d,0.00000002D,10000));}}
0.75 : 3 / 40.518518 : 37031 / 714170.9054054 : 67 / 740.142857143 : 1 / 73.141592654 : 104348 / 332152.718281828 : 23225 / 8544-0.423310825 : -1253 / 296031.415926536 : 208696 / 6643
Deriving an approximation within a specified tolerance:
(()=>{"use strict";// ---------------- APPROXIMATE RATIO ----------------// approxRatio :: Real -> Real -> RatioconstapproxRatio=epsilon=>n=>{constc=gcdApprox(0<epsilon?epsilon:(1/10000))(1,n);returnRatio(Math.floor(n/c),Math.floor(1/c));};// gcdApprox :: Real -> (Real, Real) -> RealconstgcdApprox=epsilon=>(x,y)=>{const_gcd=(a,b)=>b<epsilon?a:_gcd(b,a%b);return_gcd(Math.abs(x),Math.abs(y));};// ---------------------- TEST -----------------------// main :: IO ()constmain=()=>// Using a tolerance of 1/10000[0.9054054,0.518518,0.75].map(compose(showRatio,approxRatio(0.0001))).join("\n");// ---------------- GENERIC FUNCTIONS ----------------// compose (<<<) :: (b -> c) -> (a -> b) -> a -> cconstcompose=(...fs)=>// A function defined by the right-to-left// composition of all the functions in fs.fs.reduce((f,g)=>x=>f(g(x)),x=>x);// Ratio :: Int -> Int -> RatioconstRatio=(n,d)=>({type:"Ratio",n,d});// showRatio :: Ratio -> StringconstshowRatio=nd=>`${nd.n.toString()}/${nd.d.toString()}`;// MAIN ---returnmain();})();
67/7414/273/4
Works withjq (*)
Works with gojq, the Go implementation of jq
The following definition of `number_to_r` can be used for JSON numbers in general, as illustrated by the examples.
This entry assumes the availabilityof two functions (`r/2` and `power/1`) as defined inthe "rational" moduleatArithmetic/Rational#jq, which also provides a definitionfor `rpp/0`, a pretty-printer used in the examples.
(*) With the caveat that the C implementation of jq does not support unlimited-precision integer arithmetic.
# include "rational"; # a reminder that r/2 and power/1 are required# Input: any JSON number, not only a decimal# Output: a rational, constructed using r/2# Requires power/1 (to take advantage of gojq's support for integer arithmetic)# and r/2 (for rational number constructor)def number_to_r: # input: a decimal string # $in - either null or the original input # $e - the integer exponent of the original number, or 0 def dtor($in; $e): index(".") as $ix | if $in and ($ix == null) then $in else (if $ix then sub("[.]"; "") else . end | tonumber) as $n | (if $ix then ((length - ($ix+1)) - $e) else - $e end) as $p | if $p >= 0 then r( $n; 10|power($p)) else r( $n * (10|power(-$p)); 1) end end; . as $in | tostring | if (test("[Ee]")|not) then dtor($in; 0) else capture("^(?<s>[^eE]*)[Ee](?<e>.*$)") | (.e | if length > 0 then tonumber else 0 end) as $e | .s | dtor(null; $e) end ;Examples
0.9054054,0.518518,0.75,1e308 | "\(.) → \(number_to_r | rpp)"
0.9054054 → 4527027 // 50000000.518518 → 259259 // 5000000.75 → 3 // 41e+308 → 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 // 1
Julia has a native Rational type, and providesa convenience conversion function that implements a standard algorithm for approximating a floating-point number by a ratio of integers to within a given tolerance, which defaults to machine epsilon.
rationalize(0.9054054)rationalize(0.518518)rationalize(0.75)
4527027//5000000259259//5000003//4
Since Julia by default uses itsFloat64 type to represent floating-point numbers, if enough decimal digits are provided (so that the difference between the floating-point representation of the resulting fraction and the original number is smaller than the machine epsilon) the smaller fraction is returned, which in this case is the exact result:
julia> rationalize(0.5185185185185185)14//27julia> rationalize(0.9054054054054054)67//74
Here is the core algorithm written in Julia 1.0, without handling various data types and corner cases:
functionrat(x::AbstractFloat,tol::Real=eps(x))::Rationalp,q,pp,qq=copysign(1,x),0,0,1x,y=abs(x),1.0r,a=modf(x)nt,t,tt=tol,0.0,tolwhiler>nt# convergents of the continued fraction: np//nq = (p*a + pp) // (q*a + qq)np,nq=Int(a).*(p,q).+(pp,qq)p,pp,q,qq=np,p,nq,qx,y=y,r# instead of the inexact 1/r...a,r=divrem(x,y)t,tt=nt,t# maintain x = (p + (-1)^i * r) / qnt=a*t+ttendi=Int(cld(x-tt,y+t))# find optimal semiconvergent: smallest i such that x-i*y < i*t+ttreturn(i*p+pp)//(i*q+qq)end
// version 1.1.2classRational(valnum:Long,valden:Long){overridefuntoString()="$num/$den"}fundecimalToRational(d:Double):Rational{valds=d.toString().trimEnd('0').trimEnd('.')valindex=ds.indexOf('.')if(index==-1)returnRational(ds.toLong(),1L)varnum=ds.replace(".","").toLong()varden=1Lfor(nin1..(ds.length-index-1))den*=10Lwhile(num%2L==0L&&den%2L==0L){num/=2Lden/=2L}while(num%5L==0L&&den%5L==0L){num/=5Lden/=5L}returnRational(num,den)}funmain(args:Array<String>){valdecimals=doubleArrayOf(0.9054054,0.518518,2.405308,.75,0.0,-0.64,123.0,-14.6)for(decimalindecimals)println("${decimal.toString().padEnd(9)} = ${decimalToRational(decimal)}")}
0.9054054 = 4527027/50000000.518518 = 259259/5000002.405308 = 601327/2500000.75 = 3/40.0 = 0/1-0.64 = -16/25123.0 = 123/1-14.6 = -73/5
' Uses convention that one repeating sequence implies infinitely repeating sequence..' Non-recurring fractions are limited to nd number of digits in nuerator & denominatornd =3 ' suggest 3. 4 is slow. >4 is .......do read x$ data "0.5", "0.1", "0.333", "1 /3", "0.33", "0.14159265", "2^-0.5", "0.1 +0.9*rnd(1)" data "0.142857142857", "int( 1000*rnd(1))/int( 1000*rnd(1))","end" ' always between 0 and 0.999999... if x$ ="end" then exit do print x$; " is "; type$ =check$( x$) print type$; if type$ ="recurring" then x =val( mid$( x$, 3, ( len( x$) -2) /2)) rep =( len( x$) -2) /2 num =x den =10^rep -1 gcd =gcd( num, den) print print " Calculating exact fraction for ", recurring$( x); " recurring & found"; print num /gcd; " /"; den /gcd print else ' non-recurring. Check numerators & denominators <1000 x =eval( x$) print print " Looking for fractions that are close to "; using( "#.############", x); " & found "; eps =10^nd for n = 1 to nd for i =1 to 10^n -1 for j =i to 10^n -1 fr =i /j if abs( x -fr) <eps then eps =abs( x -fr) 'print i; " /"; j; " = ", using( "##.############", fr), "with error +/-"; using( "###.#########", eps /x *100); " %" ii =i: jj =j if eps =0 then exit for end if next j scan if eps =0 then exit for next i if eps =0 then exit for next n print ii; " /"; jj print end ifloop until 0printprint "END."endfunction recurring$( x) recurring$ ="0." do recurring$ =recurring$ +str$( x) loop until len( recurring$) >=14end functionfunction gcd( a, b) ' thanks Uncle Ben.. while b <>0 t =b b =a mod b a =t wend gcd =aend functionfunction check$( i$) check$ ="non-recurring" length =len( i$) -2 ' allow for the '0.'. if length /2 =int( length /2) then if mid$( i$, 3, length /2) =mid$( i$, 3 +length /2, length /2) then check$ ="recurring"end function
0.5 is non-recurring Looking for fractions that are close to 0.500000000000 & found 1 /20.1 is non-recurring Looking for fractions that are close to 0.100000000000 & found 1 /100.333 is non-recurring Looking for fractions that are close to 0.333000000000 & found 332 /9971 /3 is non-recurring Looking for fractions that are close to 0.333333333333 & found 1 /30.33 is recurring Calculating exact fraction for 0.333333333333 recurring & found1 /30.14159265 is non-recurring Looking for fractions that are close to 0.141592650000 & found 16 /1132^-0.5 is non-recurring Looking for fractions that are close to 0.707106781187 & found 408 /5770.1 +0.9*rnd(1) is non-recurring Looking for fractions that are close to 0.489587274383 & found 47 /960.142857142857 is recurring Calculating exact fraction for 0.142857142857 recurring & found1 /7int( 1000*rnd(1))/int( 1000*rnd(1)) is non-recurring Looking for fractions that are close to 0.032786885246 & found 2 /61END.
Brute force, and why not?
for_,vinipairs({0.9054054,0.518518,0.75,math.pi})dolocaln,d,dmax,eps=1,1,1e7,1e-15whilemath.abs(n/d-v)>epsandd<dmaxdod=d+1n=math.floor(v*d)endprint(string.format("%15.13f --> %d / %d",v,n,d))end
0.9054054000000 --> 4527027 / 50000000.5185180000000 --> 259259 / 5000000.7500000000000 --> 3 / 43.1415926535898 --> 31415926 / 10000000
moduleConvert_decimal_number_to_rational{FunctionRational(numeratorasdecimal,denominatorasdecimal=1){ifdenominator==0thendenominator=1whilefrac(numerator)<>0{numerator*=10@denominator*=10@}sgn=Sgn(numerator)*Sgn(denominator)denominator<=abs(denominator)numerator<=abs(numerator)*sgngcd1=lambda(aasdecimal,basdecimal)->{ifa<bthenswapa,bg=amodbwhileg>0@{a=b:b=g:g=amodb}' added >0@ for removing overflow.=abs(b)}gdcval=gcd1(abs(numerator),denominator)ifgdcval<denominatorandgdcval<>0thendenominator/=gdcvalnumerator/=gdcvalendif=(numerator,denominator)}PrintRational(0.9054054)#str$(" / ")="4527027 / 5000000"' truePrintRational(0.518518)#str$(" / ")="259259 / 500000"' truePrintRational(0.75)#str$(" / ")="3 / 4"' true}Convert_decimal_number_to_rational
>map(convert,[0.9054054,0.518518,0.75],'rational','exact');4527027259259[-------,------,3/4]5000000500000
Map[Rationalize[#,0]&,{0.9054054,0.518518,0.75}]->{4527027/5000000,259259/500000,3/4}
[a,b]=rat(.75)[a,b]=rat(.518518)[a,b]=rat(.9054054)
Output:
>> [a,b]=rat(.75) a = 3 b = 4 >> [a,b]=rat(.518518) a = 37031 b = 71417 >> [a,b]=rat(.9054054) a = 67 b = 74
This example isin need of improvement:
|
П0П1ИП1{x}x#014КИП4ИП110*П1БП02ИП410^xП0ПAИП1ПBИПAИПB/П9КИП9ИПAИПBПAИП9*-ПBx=020ИПAИП0ИПA/П0ИП1ИПA/П1ИП0ИП1С/ПNow the nearly equivalent program.
/*NetRexx program to convert decimal numbers to fractions ************** 16.08.2012 Walter Pachl derived from Rexx Version 2**********************************************************************/optionsreplaceformatcommentsjavacrossrefsavelogsymbolsNumericDigits10/* use "only" 10 digs of precision */ratt('0.9054054054','67/74')ratt('0.5185185185','14/27')ratt('0.75','3/4')ratt('0.905405400',' 693627417/766095958')ratt('0.9054054054','67/74')ratt('0.1428571428','1/7')ratt('35.000','35')ratt('35.001','35001/1000')ratt('0.00000000001','?')ratt('0.000001000001','1/999999')ratt(0.9054054054,'1/3')methodratt(d=Rexx,fs=Rexx)publicstaticfract=rat(d)Say' 'd'->'fractParsefractno'/'deIfde=''Thenx=noElsex=no/deIfx<>dThenSay'> '||x'is different'methodrat(in,high='')publicstatic/*********************************************************************** rat(number<,high) returns a fraction or an integer that is equal to* or approximately equal to number.* Nominator and denominator must not have more than high digits* 16.08.2012 Walter Pachl derived from Rexx Version 2**********************************************************************/ifhigh==''thenhigh=10**(digits-1)/* maximum nominator/denominator */x=in/* working copy */nom=0/* start values nominator */den=1/* denominator */tnom=1/* temp nominator */tden=0/* temp denominator */loopWhiletnom<=high&tden<=high/* nominator... not too large */n=x.trunc()/* take integer part of x */z=tnom;/* save temp nominator */tnom=n*tnom+nom;/* compute new temp nominator */nom=z/* assign nominator */z=tden;/* save temp denominator */tden=n*tden+den/* compute new temp denominato*/den=z/* assign denominator */ifn=x|tnom/tden=inthendoiftnom>high|tden>highthen/* temp value(s) too large */Leave/* don't use them */nom=tnom/* otherwise take them as */den=tden/* final values */leave/* and end the loop */endx=1/(x-n)/* compute x for next round */endIfden=1ThenReturnnom/* an integer */ElseReturnnom'/'den/* otherwise a fraction */
Output is the same as for Rexx Version 2.
Similar to the Rust and Julia implementations.
importmathimportfenvtypeRational=objectnumerator:intdenominator:intproc`$`(self:Rational):string=ifself.denominator==1:$self.numeratorelse:$self.numerator&"//"&$self.denominatorfuncrationalize(x:float,tol:float=epsilon(float)):Rational=varxx=xletflagNeg=xx<0.0ifflagNeg:xx=-xxifxx<minimumPositiveValue(float):returnRational(numerator:0,denominator:1)ifabs(xx-round(xx))<tol:returnRational(numerator:int(round(xx)),denominator:1)vara=0varb=1varc=int(ceil(xx))vard=1varaux1=high(int)div2whilec<aux1andd<aux1:varaux2=(float(a)+float(c))/(float(b)+float(d))ifabs(xx-aux2)<tol:breakifxx>aux2:inca,cincb,delse:incc,aincd,bvargcd=gcd(a+c,b+d)ifflagNeg:Rational(numerator:-(a+c)divgcd,denominator:(b+d)divgcd)else:Rational(numerator:(a+c)divgcd,denominator:(b+d)divgcd)echorationalize(0.9054054054)echorationalize(0.9054054054,0.0001)echorationalize(0.5185185185)echorationalize(0.5185185185,0.0001)echorationalize(0.75)echorationalize(0.1428571428,0.001)echorationalize(35.000)echorationalize(35.001)echorationalize(0.9)echorationalize(0.99)echorationalize(0.909)echorationalize(0.909,0.001)
2263456195//249993669367//741037026019//199997875114//273//41//73535001//10009//1099//100909//100010//11
Nim also has a rationals library for this, though it does not allow you to set tolerances like the code above.
importrationalsechotoRational(0.9054054054)echotoRational(0.5185185185)echotoRational(0.75)echotoRational(0.1428571428)echotoRational(35.000)echotoRational(35.001)echotoRational(0.9)echotoRational(0.99)echotoRational(0.909)
67/741037036407/19999987853/41/735/135001/10009/1099/100909/1000
Any number in Ol by default is exact. It means that any number automatically converted into rational form. If you want to use real floating point numbers, use "#i" prefix.
Function `exact` creates exact number (possibly rational) from any inexact.
(print(exact#i0.9054054054))(print(exact#i0.5185185185))(print(exact#i0.75))(print(exact#i35.000))(print(exact#i35.001))(print(exact#i0.9))(print(exact#i0.99))(print(exact#i0.909))
4077583446378673/45035996273704964670399613402603/90071992547409923/4354925952829924835/1407374883553288106479329266893/90071992547409924458563631096791/45035996273704964093772061279781/4503599627370496
Quick and dirty.
convert(x)={ my(n=0); while(x-floor(x*10^n)/10^n!=0.,n++); floor(x*10^n)/10^n};To convert a number into a rational with a denominator not dividing a power of 10, usecontfrac and the Gauss-Kuzmin distribution to distinguish (hopefully!) where to truncate.
##usesnumlibabc;functiontofraction(s:string):fraction;beginvarperiod:=s.IndexOf('.');result:=Frc(s.Remove(period,1).ToBigInteger,Power(10bi,s.Length-period-1));end;vardecimals:=|0.9054054,0.518518,0.75|;foreachvardecindecimalsdobeginprint(dec.ToString,'->');println(tofraction(dec.tostring));end;
0.9054054 -> 4527027/50000000.518518 -> 259259/5000000.75 -> 3/4
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.
subgcd{my($m,$n)=@_;($m,$n)=($n,$m%$n)while$n;return$m}subrat_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 fractionsubget_denom{my($num,$denom)=(1,pop@_);for(reverse@_){($num,$denom)=($denom,$_*$denom+$num);}wantarray?($num,$denom):$denom}subbest_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 ofwhile(1){# make sure it terminateslastif$limit*$denom<1;my$i=int($num/$denom);# not the right way to get limit, but it workspush@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;}subrat_string{my$n=shift;my$denom=1;my$neg;# trival xyz.0000 ... case$n=~s/\.0+$//;return$n,1unless$n=~ /\./;if($n=~ /^-/){$neg=1;$n=~s/^-//;}# shift decimal point to the right till it's gone$denom*=10while$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,$_)}
Output:
3/8 = 0.375:machine: 3/8string: 3/8approx below 100000000: 3/8137/4291 = 0.0319272896760662:machine: 2300603678209305/72057594037927936string: 159636448380331/5000000000000000approx below 100000000: 137/42911/sqrt(2) = 0.707106781186548machine: 6369051672525773/9007199254740992string: 176776695296637/250000000000000approx below 10: 5/7approx below 100: 29/41approx below 1000: 408/577approx below 10000: 5741/8119approx below 100000: 33461/47321approx below 100000000: 38613965/54608393-Pi = -3.14159265358979machine: -884279719003555/281474976710656string: -314159265358979/100000000000000approx below 10: -22 / 7approx below 100: -22 / 7approx below 1000: -355 / 113approx below 10000: -355 / 113approx below 100000: -208341 / 66317approx below 1e+06: -1146408 / 364913approx below 1e+07: -5419351 / 1725033approx below 1e+08: -245850922 / 78256779approx below 1e+09: -1881244168 / 598818617approx below 1e+10: -9978066541 / 3176117225
withjavascript_semanticsfunctiondecrat(strings)integernom=0,denom=1assert(s[1..2]="0.")fori=3tolength(s)dointegerch=s[i]assert(ch>='0'andch<='9')nom=nom*10+ch-'0'denom*=10endforreturnsq_div({nom,denom},gcd(nom,denom))endfunction?decrat("0.9054054")?decrat("0.518518")?decrat("0.75")
{4527027,5000000}{259259,500000}{3,4}functionasRational($val,$tolerance=1.e-6){if($val==(int)$val){// integerreturn$val;}$h1=1;$h2=0;$k1=0;$k2=1;$b=1/$val;do{$b=1/$b;$a=floor($b);$aux=$h1;$h1=$a*$h1+$h2;$h2=$aux;$aux=$k1;$k1=$a*$k1+$k2;$k2=$aux;$b=$b-$a;}while(abs($val-$h1/$k1)>$val*$tolerance);return$h1.'/'.$k1;}echoasRational(1/5)."\n";// "1/5"echoasRational(1/4)."\n";// "1/4"echoasRational(1/3)."\n";// "1/3"echoasRational(5)."\n";// "5"
(size, fofl):Convert_Decimal_To_Rational: procedure options (main); /* 14 January 2014, from Ada */Real_To_Rational: procedure (R, Bound, Numerator, Denominator) recursive options (reorder); declare R float (18), Bound float, (Numerator, Denominator) fixed binary (31); declare Error float; declare Best fixed binary initial (1); declare Best_Error float initial (huge(error)); declare I fixed binary (31); if R = 0 then do; Numerator = 0; Denominator = 1; return; end; else if R < 0 then do; call Real_To_Rational(-R, Bound, Numerator, Denominator); Numerator = -Numerator; return; end; else do I = 1 to Bound; Error = abs(I * R - trunc(I * R + sign(R)*0.5)); if Error < Best_Error then do; Best = I; Best_Error = Error; end; end; Denominator = Best; Numerator = Denominator * R + sign(R) * 0.5;end Real_To_Rational; declare (Num, Denom) fixed binary (31); declare R float (18); declare I fixed BINARY; do R = 0.75, 0.25, 0.3333333, 0.518518000, 0.905405400, 0.142857143, 3.141592654, 2.718281828, -0.423310825, 31.415926536, 0; put skip edit(R) (f(13,9)); do I = 0 to 4; call Real_to_Rational(R, 10**I, Num, Denom); put edit(' ' || trim(Num) || ' / ' || trim(Denom)) (a); end; end;end Convert_Decimal_To_Rational;Output:
0.750000000 1 / 1 3 / 4 3 / 4 3 / 4 3 / 4 0.250000000 0 / 1 1 / 4 1 / 4 1 / 4 1 / 4 0.333333300 0 / 1 1 / 3 1 / 3 1 / 3 1 / 3 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 0 / 1 0 / 1 0 / 1 0 / 1 0 / 1
require"rat"localfmt=require"fmt"localtests={0.9054054,0.518518,0.75}fortestsastestdolocalr=rat.decimal(test)fmt.print("%-9s -> %s",test,r)end
0.9054054 -> 4527027/50000000.518518 -> 259259/5000000.75 -> 3/4
Procedure.iggT(a.i,b.i)Definet.i:Ifa<b:Swapa,b:EndIfWhilea%b:t=a:a=b:b=t%a:Wend:ProcedureReturnbEndProcedureProcedure.sDec2Rat(dn.d)Definenk$,gt.i,res$nk$=Trim(StringField(StrD(dn),2,"."),"0")gt=ggT(Val(nk$),Int(Pow(10.0,Len(nk$))))res$=Str(Val(nk$)/gt)+"/"+Str(Int(Pow(10.0,Len(nk$)))/gt)ProcedureReturnres$EndProcedureOpenConsole()Defined.dRepeatRead.dd:IfNot(d>0.0Andd<1.0):Break:EndIfPrint(LSet(StrD(d),15," ")+" -> "+#TAB$+Dec2Rat(d)+#CRLF$)ForEverInput():EndDataSectionData.d0.9054054,0.518518,0.75,0.0EndDataSection
0.9054054 -> 4527027/50000000.518518 -> 259259/5000000.75 -> 3/4
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.
>>>fromfractionsimportFraction>>>fordin(0.9054054,0.518518,0.75):print(d,Fraction.from_float(d).limit_denominator(100))0.905405467/740.51851814/270.753/4>>>fordin'0.9054054 0.518518 0.75'.split():print(d,Fraction(d))0.90540544527027/50000000.518518259259/5000000.753/4>>>
Or, writing our ownapproxRatio function:
'''Approximate rationals from decimals'''frommathimport(floor,gcd)importsys# approxRatio :: Float -> Float -> RatiodefapproxRatio(epsilon):'''The simplest rational approximation to n within the margin given by epsilon. '''defgcde(e,x,y):def_gcd(a,b):returnaifb<eelse_gcd(b,a%b)return_gcd(abs(x),abs(y))returnlambdan:(lambdac=(gcde(epsilonif0<epsilonelse(0.0001),1,n)):ratio(floor(n/c))(floor(1/c)))()# main :: IO ()defmain():'''Conversions at different levels of precision.'''xs=[0.9054054,0.518518,0.75]print(fTable(__doc__+' (epsilon of 1/10000):\n')(str)(lambdar:showRatio(r)+' -> '+repr(fromRatio(r)))(approxRatio(1/10000))(xs))print('\n')e=minBound(float)print(fTable(__doc__+' (epsilon of '+repr(e)+'):\n')(str)(lambdar:showRatio(r)+' -> '+repr(fromRatio(r)))(approxRatio(e))(xs))# GENERIC -------------------------------------------------# fromRatio :: Ratio Int -> FloatdeffromRatio(r):'''A floating point value derived from a a rational value. '''returnr.get('numerator')/r.get('denominator')# minBound :: Bounded Type -> adefminBound(t):'''Minimum value for a bounded type.'''maxsize=sys.maxsizefloat_infomin=sys.float_info.minreturn{int:(-maxsize-1),float:float_infomin,bool:False,str:chr(0)}[t]# ratio :: Int -> Int -> Ratio Intdefratio(n):'''Rational value constructed from a numerator and a denominator. '''defgo(n,d):g=gcd(n,d)return{'type':'Ratio','numerator':n//g,'denominator':d//g}returnlambdad:go(n*signum(d),abs(d))# showRatio :: Ratio -> StringdefshowRatio(r):'''String representation of the ratio r.'''d=r.get('denominator')returnstr(r.get('numerator'))+(' / '+str(d)if1!=delse'')# signum :: Num -> Numdefsignum(n):'''The sign of n.'''return-1if0>nelse(1if0<nelse0)# DISPLAY -------------------------------------------------# fTable :: String -> (a -> String) -># (b -> String) -> (a -> b) -> [a] -> StringdeffTable(s):'''Heading -> x display function -> fx display function -> f -> xs -> tabular string. '''defgo(xShow,fxShow,f,xs):ys=[xShow(x)forxinxs]w=max(map(len,ys))returns+'\n'+'\n'.join(map(lambdax,y:y.rjust(w,' ')+' -> '+fxShow(f(x)),xs,ys))returnlambdaxShow:lambdafxShow:lambdaf:lambdaxs:go(xShow,fxShow,f,xs)# MAIN ---if__name__=='__main__':main()
Approximate rationals from decimals (epsilon of 1/10000):0.9054054 -> 67 / 74 -> 0.9054054054054054 0.518518 -> 14 / 27 -> 0.5185185185185185 0.75 -> 3 / 4 -> 0.75Approximate rationals from decimals (epsilon of 2.2250738585072014e-308):0.9054054 -> 4077583422059235 / 4503599627370496 -> 0.9054054 0.518518 -> 2335197471584895 / 4503599627370496 -> 0.518518 0.75 -> 3 / 4 -> 0.75
ratio<-function(decimal){denominator=1while(nchar(decimal*denominator)!=nchar(round(decimal*denominator))){denominator=denominator+1}str=paste(decimal*denominator,"/",sep="")str=paste(str,denominator,sep="")return(str)}
> ratio(.75)[1] "3/4"> ratio(0.9054054)[1] "4527027/5e+06"> ratio(3.14)[1] "157/50"
Using the Quackery big number rational arithmetic librarybigrat.qky.
[ $ "bigrat.qky" loadfile ] now! [ dup echo$ say " is " $->v drop dup 100 > if [ say "approximately " proper 100 round improper ] vulgar$ echo$ say "." cr ] is task ( $ --> )$ "0.9054054 0.518518 0.75" nest$ witheach task
0.9054054 is approximately 67/74.0.518518 is approximately 14/27.0.75 is 3/4.
Racket has builtin exact and inexact representantions of numbers, 3/4 is a valid number syntactically, and one can change between the exact and inexact values with the functions showed in the example.They have some amount of inaccuracy, but i guess it can be tolerated.
#langracket(inexact->exact0.75); -> 3/4(exact->inexact3/4); -> 0.75(exact->inexact67/74); -> 0.9054054054054054(inexact->exact0.9054054054054054);-> 8155166892806033/9007199254740992
(formerly Perl 6)Decimals are natively represented as rationals in Raku, so if the task does not need to handle repeating decimals, it is trivially handled by the.nude method, which returns the numerator and denominator:
say .nude.join('/')for0.9054054,0.518518,0.75;
4527027/5000000259259/5000003/4
However, if we want to take repeating decimals into account, then we can get a bit fancier.
subdecimal_to_fraction (Str$n,Int$rep_digits =0 )returnsStr {my ($int,$dec ) = ($n ~~ /^ (\d+) \. (\d+) $/ )».Strordie;my ($numer,$denom ) = ($dec,10 **$dec.chars );if$rep_digits {my$to_move =$dec.chars -$rep_digits;$numer -=$dec.substr(0,$to_move);$denom -=10 **$to_move; }my$rat =Rat.new($numer.Int,$denom.Int ).nude.join('/');return$int >0 ??"$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 );}
0.9054 with 3 repeating digits = 67/740.518 with 3 repeating digits = 14/270.75 with 0 repeating digits = 3/412.34567 with 0 repeating digits = 12 34567/10000012.34567 with 1 repeating digits = 12 31111/9000012.34567 with 2 repeating digits = 12 17111/4950012.34567 with 3 repeating digits = 12 1279/3700
This REXX example supports almost any form of numeric input, some examples are:
─── where:
REXX can support almost any number of decimal digits, but 10 was chosen for practicality for this task.
/*REXX program converts a rational fraction [n/m] (or nnn.ddd) to it's lowest terms.*/numericdigits10/*use ten decimal digits of precision. */parseargorig1n.1"/"n.2;ifn.2=''thenn.2=1/*get the fraction.*/ifn.1=''thencaller'no argument specified.'doj=1for2;if\datatype(n.j,'N')thencaller"argument isn't numeric:"n.jend/*j*//* [↑] validate arguments: n.1 n.2 */ifn.2=0thencaller"divisor can't be zero."/*Whoa! We're dividing by zero ! */say'old ='space(orig)/*display the original fraction. */say'new ='rat(n.1/n.2)/*display the result ──► terminal. */exit/*stick a fork in it, we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/er:say;say'***error***';say;sayarg(1);say;exit13/*──────────────────────────────────────────────────────────────────────────────────────*/rat:procedure;parseargx1_x,y;ify==''theny=10**(digits()-1)b=0;g=0;a=1;h=1/* [↑] Y is the tolerance.*/dowhilea<=y&g<=y;n=trunc(_x)_=a;a=n*a+b;b=__=g;g=n*g+h;h=_ifn=_x|a/g=xthendo;ifa>y|g>ytheniterateb=a;h=g;leaveend_x=1/(_x-n)end/*while*/ifh==1thenreturnb/*don't return number ÷ by 1.*/returnb'/'h/*proper or improper fraction. */
output when using various inputs (which are displayed as part of the output):
(Multiple runs are shown, outputs are separated by a blank line.)
old = 0.9054054054new = 67/74old = 0.5185185185new = 14/27old = 0.75new = 3/4old = 0.905405400new = 693627417/766095958old = 0.9054054054new = 67/74old = 0.1428571428new = 1/7
/*REXX program to convert decimal numbers to fractions ***************** 15.08.2012 Walter Pachl derived from above for readability* It took me time to understand :-) I need descriptive variable names* Output shows where the fraction only approximates the number* due to the limit (high) imposed on nominator and denominator**********************************************************************/NumericDigits10/* use "only" 10 digs of precision */Calltest'0.9054054054','67/74'Calltest'0.5185185185','14/27'Calltest'0.75','3/4'Calltest'0.905405400',' 693627417/766095958'Calltest'0.9054054054','67/74'Calltest'0.1428571428','1/7'Calltest'35.000','35'Calltest'35.001','35001/1000'Calltest'0.00000000001','?'Calltest'0.000001000001','1/999999'Exittest:/*********************************************************************** Test driver for rat**********************************************************************/ParseArgd,fs/* number and expected fraction */fh=rat(d)/* convert number to fracrion */Callo' 'dfhIffh<>fsThenCallo' not='fsinterpret'x='fh/* compute value of fraction */Ifx<>dThen/* not exactly equal to number */Callo'> '||x'is different'Callo' 'Returno:Sayarg(1);Returnrat:procedure/*********************************************************************** rat(number<,high) returns a fraction or an integer that is equal to* or approximately equal to number.* Nominator and denominator must not have more than high digits* 15.08.2012 Walter Pachl derived from Version 1**********************************************************************/parseargin,highx=in/* working copy */ifhigh==''thenhigh=10**(digits()-1)/* maximum nominator/denominator */nom=0/* start values nominator */den=1/* denominator */tnom=1/* temp nominator */tden=0/* temp denominator */doWhiletnom<=high&tden<=high/* nominator... not too large */n=trunc(x)/* take integer part of x */z=tnom;/* save temp nominator */tnom=n*tnom+nom;/* compute new temp nominator */nom=z/* assign nominator */z=tden;/* save temp denominator */tden=n*tden+den/* compute new temp denominato*/den=z/* assign denominator */ifn=x|tnom/tden=inthendoiftnom>high|tden>highthen/* temp value(s) too large */Leave/* don't use them */nom=tnom/* otherwise take them as */den=tden/* final values */leave/* and end the loop */endx=1/(x-n)/* compute x for next round */endifden=1thenreturnnom/* denominator 1: integer */returnnom'/'den/* otherwise a fraction */
Output:
0.9054054054 67/74 0.5185185185 14/27 0.75 3/4 0.905405400 693627417/766095958> 0.9054053996 is different 0.9054054054 67/74 0.1428571428 1/7> 0.1428571429 is different 35.000 35 35.001 35001/1000 0.00000000001 0 not=?> 0 is different 0.000001000001 1/999999
/* REXX ---------------------------------------------------------------* 13.02.2014 Walter Pachl* specify the number as xxx.yyy(pqr) pqr is the period* for the number xxx.yyypqrpqrpqrpqrpqr...*--------------------------------------------------------------------*/NumericDigits100Calltest'5.55555','111111/20000'Calltest'3','3'Calltest'0.03','3/100'Calltest'0.9(054)','67/74'Calltest'0.(3)','1/3'Calltest'5.28(571428)','37/7'Calltest'5.28(571428)','38/7 (demonstrate error case)'Calltest'0.(518)','14/27'Calltest'0.75','3/4'Calltest'0.(142857)','1/7'Calltest'0.1(428571)','1/7'Calltest'35.000','35'Calltest'35.001','35001/1000'Calltest'0.00000000001','1/100000000000'Calltest'0.000001000001','1000001/1000000000000'Exittest:ParseArgz,sollzin=zIfpos('(',z)=0ThenDoParseVarzi'.'fz=i||fn=10**length(f)EndElseDolp=pos('(',z)-3rp=pos(')',z)-4x=space(translate(z,' ','()'),0)z1=x*10**lpParseVarz1z1'.'z2=x*10**rpz=z2-z1n=10**rp-10**lpEnddd=gcd(z,n)zz=z/ddnn=n/ddIfnn=1Thenfract=zzElsefract=zz'/'nnIffract==sollThentag='ok'Elsetag='should be'sollsayzin'='fracttagReturnGCD:procedure/*********************************************************************** Recursive procedure**********************************************************************/ParseArga,bifb=0thenreturnabs(a)returnGCD(b,a//b)
Output:
5.55555 = 111111/20000 ok3 = 3 ok0.03 = 3/100 ok0.9(054) = 67/74 ok0.(3) = 1/3 ok5.28(571428) = 37/7 ok5.28(571428) = 37/7 should be 38/7 (demonstrate error case)0.(518) = 14/27 ok0.75 = 3/4 ok0.(142857) = 1/7 ok0.1(428571) = 1/7 ok35.000 = 35 ok35.001 = 35001/1000 ok0.00000000001 = 1/100000000000 ok0.000001000001 = 1000001/1000000000000 ok
Starting with HP-48 versions, the conversion can be performed directly with the→Q instruction. Earlier versions must instead use the following code, which is based on continued fractions.
| RPL code | Comment |
|---|---|
≪ ABS LAST SIGN 1E6 → sign dmax ≪ (0,1) (1,0)DO SWAP OVER 4 ROLL INV IP LAST FP 5 ROLLD * +UNTIL DUP2 IM SWAP IM * dmax > 4 PICK dmax INV < OREND ROT ROT DROP2 "'" OVER RE sign * →STR + "/" + SWAP IM →STR + STR→ ≫ ≫ '→PQ' STO | →PQ( x → 'p/q' )store sign(x) and max denominatora(0) = x ; hk(-2) = (0,1) ; hk(-1) = (1,0)loop reorder int(a(n)), hk(n-1) and hk(n-2) in stack a(n+1)=1/frac(a(n)) back to top of stack hk(n) = a(n)*hk(n-1) + hk(n-2) until k(n)*(kn-1) > max denominator or a(n+1) > max denominatorclean stackconvert a(n) from (p,q) to 'p/q' formatreturn 'p/q' |
.518518→PQ.905405405405→PQ-3.875→PQ
Output:
3: '37031/71417' 2: '67/74' 1: '-31/8'
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.
>'0.9054054 0.518518 0.75'.split.each{|d|puts"%s %s"%[d,Rational(d)]}0.90540544527027/50000000.518518259259/5000000.753/4=>["0.9054054","0.518518","0.75"]
This loop finds the simplest fractions within a given radius, because the floating-point representation is not exact.
[0.9054054,0.518518,0.75].each{|f|puts"#{f}#{f.rationalize(0.0001)}"}# =>0.9054054 67/74# =>0.518518 14/27# =>0.75 3/4
A suffix for integer and float literals was introduced:
2.1.0p0 :001 > 0.9054054r => (4527027/5000000) 2.1.0p0 :002 > 0.518518r => (259259/500000) 2.1.0p0 :003 > 0.75r => (3/4)
extern crate rand;extern crate num;use num::Integer;use rand::Rng;fn decimal_to_rational (mut n : f64) -> [isize;2] { //Based on Farey sequences assert!(n.is_finite()); let flag_neg = n < 0.0; if flag_neg { n = n*(-1.0) } if n < std::f64::MIN_POSITIVE { return [0,1] } if (n - n.round()).abs() < std::f64::EPSILON { return [n.round() as isize, 1] } let mut a : isize = 0; let mut b : isize = 1; let mut c : isize = n.ceil() as isize; let mut d : isize = 1; let aux1 = isize::max_value()/2; while c < aux1 && d < aux1 { let aux2 : f64 = (a as f64 + c as f64)/(b as f64 + d as f64); if (n - aux2).abs() < std::f64::EPSILON { break } if n > aux2 { a = a + c; b = b + d; } else { c = a + c; d = b + d; } } // Make sure that the fraction is irreducible let gcd = (a+c).gcd(&(b+d)); if flag_neg { [-(a + c)/gcd, (b + d)/gcd] } else { [(a + c)/gcd, (b + d)/gcd] }} #[test]fn test1 () { // Test the function with 1_000_000 random decimal numbers let mut rng = rand::thread_rng(); for _i in 1..1_000_000 { let number = rng.gen::<f64>(); let result = decimal_to_rational(number); assert!((number - (result[0] as f64)/(result[1] as f64)).abs() < std::f64::EPSILON); assert!(result[0].gcd(&result[1]) == 1); }}fn main () { let mut rng = rand::thread_rng(); for _i in 1..10 { let number = rng.gen::<f64>(); let result = decimal_to_rational(number); if result[1] == 1 { println!("{} -> {}", number, result[0]) } else { println!("{} -> {}/{}", number, result[0], result[1]) } } for i in [-0.9054054, 0.518518, -0.75, 0.5185185185185185, -0.9054054054054054, 0.0, 1.0, 2.0].iter() { let result = decimal_to_rational(*i as f64); if result[1] == 1 { println!("{} = {}",*i, result[0]) } else { println!("{} = {}/{}", *i, result[0], result[1]) } }}First test the function with 1_000_000 random double floats :
running 1 testtest test1 ... oktest result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Now run it with 10 random double floats and some selected ones printing the results
0.47783621261626297 -> 36036136/754152470.29135687639237284 -> 164756020/5654783990.04962905490905656 -> 4105111/827158810.33418703921783965 -> 16612678/497107190.07284921759788943 -> 6252865/858329740.783712619202954 -> 62096920/792342990.3788902482801324 -> 30401287/802377130.03780115715370047 -> 1522201/402686350.9975233883406127 -> 79858287/80056556-0.9054054 -> -4527027/50000000.518518 -> 259259/500000-0.75 -> -3/40.5185185185185185 -> 14/27-0.9054054054054054 -> -67/740 -> 01 -> 12 -> 2
Best seen running in your browserScastie (remote JVM).
importorg.apache.commons.math3.fraction.BigFractionobjectNumber2FractionextendsApp{valn=Array(0.750000000,0.518518000,0.905405400,0.142857143,3.141592654,2.718281828,-0.423310825,31.415926536)for(d<-n)println(f"$d%-12s :${newBigFraction(d,0.00000002D,10000)}%s")}
The librarybigrat.s7idefines the functionbigRational,which creates abigRational number from a string.This function accepts, besides fractions, also a decimal number with repeating decimals.Internally a bigRational uses numerator and denominator to represent a rational number.Writing a bigRational does not create a fraction with numerator and denominator, but a decimal number with possibly repeating decimals.The functionfractionuses numerator and denominator from the bigRational number to get a string with the fraction.
$ include "seed7_05.s7i"; include "bigrat.s7i";const proc: main is func begin writeln(bigRational parse "0.9(054)"); writeln(bigRational parse "0.(518)"); writeln(bigRational parse "0.75"); writeln(bigRational parse "3.(142857)"); writeln(bigRational parse "0.(8867924528301)"); writeln(bigRational parse "0.(846153)"); writeln(bigRational parse "0.9054054"); writeln(bigRational parse "0.518518"); writeln(bigRational parse "0.14285714285714"); writeln(bigRational parse "3.14159265358979"); writeln(bigRational parse "2.718281828"); writeln(bigRational parse "31.415926536"); writeln(bigRational parse "0.000000000"); writeln; writeln(fraction(bigRational("0.9(054)"))); writeln(fraction(bigRational("0.(518)"))); writeln(fraction(bigRational("0.75"))); writeln(fraction(bigRational("3.(142857)"))); writeln(fraction(bigRational("0.(8867924528301)"))); writeln(fraction(bigRational("0.(846153)"))); writeln(fraction(bigRational("0.9054054"))); writeln(fraction(bigRational("0.518518"))); writeln(fraction(bigRational("0.14285714285714"))); writeln(fraction(bigRational("3.14159265358979"))); writeln(fraction(bigRational("2.718281828"))); writeln(fraction(bigRational("31.415926536"))); writeln(fraction(bigRational("0.000000000"))); end func;0.9(054)0.(518)0.753.(142857)0.(8867924528301)0.(846153)0.90540540.5185180.142857142857143.141592653589792.71828182831.4159265360.067/7414/273/422/747/5311/134527027/5000000259259/5000007142857142857/50000000000000314159265358979/100000000000000679570457/2500000003926990817/1250000000/1
By default, literal numbers are represented in rational form:
say0.75.as_frac#=> 3/4say0.518518.as_frac#=> 259259/500000say0.9054054.as_frac#=> 4527027/5000000
Additionally,Num(str) can be used for parsing a decimal expansion into rational form:
'0.9054054 0.518518 0.75'.split.each{|str|sayNum(str).as_frac}
4527027/5000000259259/5000003/4
For rational approximations, the Number.rat_approx method can be used:
say0.518518.rat_approx.as_frac#=> 14/27say0.9054054.rat_approx.as_frac#=> 67/74
\( convert float to rational (built-in) rationals are automatically reduced and converted to integer if possible\)main(parms):+ inp =: 0.009054054, 0.518518, 0.75, -3.141592, 12.0319272, 230.0 for f =: tuple inp give values print f, '=', float f as rational \ not (yet) in the standard library:float (@) as rational: m, e =: float @ split decimal \ library function does the work return m * 10^e
0.00905405 = 4527027/5000000000.518518 = 259259/5000000.75 = 3/4-3.14159 = -392699/12500012.0319 = 15039909/1250000230.0 = 230
\( convert decimal string to reduced rational and print\)main(parms):+ inp =: "0.009054054", "0.518518", "0.752", "-3.141592", "12.0319272", "30.0" for f =: tuple inp give values r =: string f as pair print f, '=', join r by '/'\ convert decimal number from string to numerator and denominatorstring (str) as pair: intfrac =: string str split by '.' ? intfrac.Count ~= 2 :> str \ nor single decimal point int =: string intfrac.1 as integer frac =: string intfrac.2 as integer den =: 10^(intfrac.2.Count) num =: int * den + frac gcd =: integer den, num gcd ? gcd > 1 num =: num // gcd den =: den // gcd :> num, den
0.009054054 = 4527027/5000000000.518518 = 259259/5000000.752 = 94/125-3.141592 = -357301/12500012.0319272 = 15039909/125000030.0 = 30/1
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 onhttp://wiki.tcl.tk/752:
#!/usr/bin/env tclshprocdbl2frac{dbl{eps0.000001}}{for{setden1}{$den<1024}{incrden}{setnum[expr{round($dbl*$den)}]if{abs(double($num)/$den-$dbl)<$eps}break}list$num$den}#-------------------- That's all... the rest is the test suiteif{[filetail$argv0]eq[filetail[infoscript]]}{foreach{test->expected}{{dbl2frac0.518518}->{4281}{dbl2frac0.75}->{34}{dbl2frac0.9054054}->{6774}}{catch$testresif{$resne$expected}{puts"$test -> $res, expected $expected"}}}
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.tcldbl2frac 0.518518 -> 14 27, expected 42 81~ $
| Display | Key | Display | Key | Display | Key | Display | Key |
|---|---|---|---|---|---|---|---|
| 00 33 | STO | 25 00 | 0 | 50 | 75 | ||
| 01 00 | 0 | 26 64 | * | 51 | 76 | ||
| 02 00 | 0 | 27 34 | RCL | 52 | 77 | ||
| 03 33 | STO | 28 01 | 1 | 53 | 78 | ||
| 04 01 | 1 | 29 94 | = | 54 | 79 | ||
| 05 56 | *CP | 30 41 | R/S | 55 | 80 | ||
| 06 01 | 1 | 31 | 56 | 81 | |||
| 07 35 | SUM | 32 | 57 | 82 | |||
| 08 01 | 1 | 33 | 58 | 83 | |||
| 09 34 | RCL | 34 | 59 | 84 | |||
| 10 01 | 1 | 35 | 60 | 85 | |||
| 11 64 | * | 36 | 61 | 86 | |||
| 12 34 | RCL | 37 | 62 | 87 | |||
| 13 00 | 0 | 38 | 63 | 88 | |||
| 14 94 | = | 39 | 64 | 89 | |||
| 15 12 | Inv | 40 | 65 | 90 | |||
| 16 29 | *Int | 41 | 66 | 91 | |||
| 17 12 | Inv | 42 | 67 | 92 | |||
| 18 37 | *x=t | 43 | 68 | 93 | |||
| 19 00 | 0 | 44 | 69 | 94 | |||
| 20 06 | 6 | 45 | 70 | 95 | |||
| 21 34 | RCL | 46 | 71 | 96 | |||
| 22 01 | 1 | 47 | 72 | 97 | |||
| 23 32 | x<>t | 48 | 73 | 98 | |||
| 24 34 | RCL | 49 | 74 | 99 |
Asterisk denotes 2nd function key.
| 0: Decimal | 1: Denominator | 2: Unused | 3: Unused | 4: Unused |
| 5: Unused | 6: Unused | 7: Unused | 8: Unused | 9: Unused |
Annotated listing:
STO 0 // Decimal := User Input0 STO 1 // Denominator := 0*CP // RegT := 01 SUM 1 // Denominator += 1RCL 1 * RCL 0 = Inv *Int // Find fractional part of Decimal * DenominatorInv *x=t 0 6 // If it is nonzero loop back to instruction 6RCL 1 x<>t // Report denominatorRCL 0 * RCL 1 = // Report numeratorR/S // End
Usage:
Enter the decimal and then press RST R/S. Once a suitable rational is found, the numerator will be displayed. Press x<>t to toggle between the numerator and denominator.
0.875 RST R/S
After about five seconds,3 will appear on the screen. Press x<>t and8 will appear on the screen. The fraction is 3/8.
Any fraction with denominator <=100 is found in 1 minute or less. 100 denominators are checked per minute.
structFraction{publiclongd;publiclongn;}Fractionrat_approx(doublef,longmd){longa;long[]h={0,1,0};long[]k={1,0,0};longx,d,n=1;boolneg=false;if(md<=1)return{1,(long)f};if(f<0){neg=true;f=-f;}while(f!=Math.floor(f)){n<<=1;f*=2;}d=(long)f;for(inti=0;i<64;i++){a=(n!=0)?d/n:0;if(i!=0&&a==0)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;elsebreak;}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];}return{k[1],neg?-h[1]:h[1]};}voidmain(){doublef;print("f = %16.14f\n",f=1.0/7);for(inti=1;i<20000000;i*=16){print("denom <= %11d: ",i);varr=rat_approx(f,i);print("%11ld/%ld\n",r.n,r.d);}print("f = %16.14f\n",f=Math.atan2(1,1)*4);for(inti=1;i<20000000;i*=16){print("denom <= %11d: ",i);varr=rat_approx(f,i);print("%11ld/%ld\n",r.n,r.d);}}
f = 0.14285714285714denom <= 1: 0/1denom <= 16: 1/7denom <= 256: 1/7denom <= 4096: 1/7denom <= 65536: 1/7denom <= 1048576: 1/7denom <= 16777216: 1/7f = 3.14159265358979denom <= 1: 3/1denom <= 16: 22/7denom <= 256: 355/113denom <= 4096: 355/113denom <= 65536: 104348/33215denom <= 1048576: 3126535/995207denom <= 16777216: 47627751/15160384
FunctionReal2Rational(rAsDouble,boundAsLong)AsStringIfr=0ThenReal2Rational="0/1"ElseIfr<0ThenResult=Real2Rational(-r,bound)Real2Rational="-"&ResultElsebest=1bestError=1E+99Fori=1Tobound+1currentError=Abs(i*r-Round(i*r))IfcurrentError<bestErrorThenbest=ibestError=currentErrorIfbestError<1/boundThenGoToSkipLoopEndIfNextiSkipLoop:Real2Rational=Round(best*r)&"/"&bestEndIfEndFunctionSubTestReal2Rational()Debug.Print"0.75"&":";Fori=0To5Order=CDbl(10)^CDbl(i)Debug.Print" "&Real2Rational(0.75,CLng(Order));NextiDebug.PrintDebug.Print"0.518518"&":";Fori=0To5Order=CDbl(10)^CDbl(i)Debug.Print" "&Real2Rational(0.518518,CLng(Order));NextiDebug.PrintDebug.Print"0.9054054"&":";Fori=0To5Order=CDbl(10)^CDbl(i)Debug.Print" "&Real2Rational(0.9054054,CLng(Order));NextiDebug.PrintDebug.Print"0.142857143"&":";Fori=0To5Order=CDbl(10)^CDbl(i)Debug.Print" "&Real2Rational(0.142857143,CLng(Order));NextiDebug.PrintDebug.Print"3.141592654"&":";Fori=0To5Order=CDbl(10)^CDbl(i)Debug.Print" "&Real2Rational(3.141592654,CLng(Order));NextiDebug.PrintDebug.Print"2.718281828"&":";Fori=0To5Order=CDbl(10)^CDbl(i)Debug.Print" "&Real2Rational(2.718281828,CLng(Order));NextiDebug.PrintDebug.Print"-0.423310825"&":";Fori=0To5Order=CDbl(10)^CDbl(i)Debug.Print" "&Real2Rational(-0.423310825,CLng(Order));NextiDebug.PrintDebug.Print"31.415926536"&":";Fori=0To5Order=CDbl(10)^CDbl(i)Debug.Print" "&Real2Rational(31.415926536,CLng(Order));NextiEndSub
0.75: 1/1 3/4 3/4 3/4 3/4 3/40.518518: 1/1 1/2 14/27 14/27 14/27 37031/714170.9054054: 1/1 1/1 67/74 67/74 67/74 67/740.142857143: 0/1 1/7 1/7 1/7 1/7 1/73.141592654: 3/1 22/7 22/7 355/113 355/113 104348/332152.718281828: 3/1 19/7 193/71 1457/536 23225/8544 173459/63812-0.423310825: -0/1 -3/7 -11/26 -69/163 -1253/2960 -10093/2384331.415926536: 31/1 157/5 377/12 3550/113 208696/6643 1563445/49766
import"./rat"forRatimport"./fmt"forFmtvartests=[0.9054054,0.518518,0.75]for(testintests){varr=Rat.fromFloat(test)System.print("%(Fmt.s(-9,test)) ->%(r)")}
0.9054054 -> 4527027/50000000.518518 -> 259259/5000000.75 -> 3/4
fcn real2Rational(r,bound){ if (r == 0.0) return(0,1); if (r < 0.0){ result := real2Rational(-r, bound); return(-result[0],result[1]); } else { best,bestError := 1,(1.0).MAX; foreach i in ([1 .. bound + 1]){ error := (r*i - (r*i).round()).abs(); if (error < bestError) best,bestError = i,error; } return((r*best).round().toInt(),best); }}tests := T(0.750000000, 0.518518000, 0.905405400, 0.142857143, 3.141592654, 2.718281828, -0.423310825, 31.415926536);foreach r in (tests) { print("%8.9f ".fmt(r)); foreach i in (6) { print(" %d/%d".fmt(real2Rational(r,(10).pow(i)).xplode())) } println();}0.750000000 1/1 3/4 3/4 3/4 3/4 3/40.518518000 1/2 1/2 14/27 14/27 14/27 37031/714170.905405400 1/1 10/11 67/74 67/74 67/74 67/740.142857143 0/1 1/7 1/7 1/7 1/7 1/73.141592654 3/1 22/7 22/7 355/113 355/113 104348/332152.718281828 3/1 19/7 193/71 2721/1001 25946/9545 222630/81901-0.423310825 -1/2 -3/7 -11/26 -69/163 -1253/2960 -10093/2384331.415926536 63/2 157/5 3173/101 3550/113 208696/6643 2918194/92889