Decimal To Fraction Conversion - A Simpler VersionDate: 11/25/2002 at 04:06:24 From: Paul Bearne Subject: Decimal To Fraction Conversion In your thread Decimal To Fraction Conversion http://mathforum.org/library/drmath/view/51886.html you did some code in C++. Do you know if this has been or can be written in javasrcipt and PHP? I need to do this for a recipe System I am helping code. Thanks for any help. Date: 11/25/2002 at 12:05:48 From: Doctor Peterson Subject: Re: Decimal To Fraction Conversion Hi, Paul. I don't know the particular languages you want, but it should be no trouble to write this algorithm in any language, if you know enough C++ to discern what the algorithm is, or if I rewrite it in pseudocode. But since that page was written a long time ago, I'd like instead to show you a much simpler version of the algorithm, based on the explanation given in our FAQ (section IIc): Fractions, Decimals, Percentages http://mathforum.org/dr.math/faq/faq.fractions.html The example given there is to find the fraction for F = 0.127569574. n Quotient a(n) Fraction Reciprocal Value So Far 0/1 (start) 1/0 0 0.127569574 0 0.127569574 7.833333362 0/1 = (0+0*1)/(1+0*0) 1 7.833333362 7 0.833333362 1.199999959 1/7 = (1+7*0)/(0+7*1) 2 1.199999959 1 0.199999959 5.000001034 1/8 = (0+1*1)/(1+1*7) 3 5.000001034 5 0.000001034 Stop 6/47 = (1+5*1)/(7+5*8) The work at each step is n q int(q) q-a 1/(q-a) num=num1+a*num2 [a] [new q] den=den1+a*den2 num1=num2, den1=den2 num2=num, den2=den Here we start with (num1,den1) = (0,1) and (num2,den2) = (1,0), and keep them equal to the last two fractions obtained; at each step, they are used to find the new fraction. So the algorithm looks like this: tofrac(dec) [dec is the (decimal) number to be converted] { num1 = 0 [these are integers] den1 = 1 num2 = 1 den2 = 0 q = dec [q is a float, the current value being worked on] n = 0 loop { n = n + 1 if (q > max_int) [prevent overflow] exit loop a = int(q) [a is an integer] num = num1 + a * num2 den = den1 + a * den2 if (q - a < epsilon) [prevent divide by zero] exit loop q = 1 / (q - a) num1 = num2 den1 = den2 num2 = num den2 = den } until((abs(num/den - dec) < epsilon) [stop when close enough] or (n > max_steps) [avoid infinite loops] or (num > max_numerator) [stop if too big] or (den > max_denominator)) return num, den } As before, I don't have a lot of experience with this algorithm, to know whether the condition for stopping is robust enough. I did test it in Visual Basic to see that it works for cases like pi, sqrt(2), 1/7, and approximations to them like 0.142857, each of which has a different peculiarity. You'll probably have to do some more work; for example, this doesn't really return numerator and denominator smaller than the maximum, but just stops if they go beyond, as a safety limit. If you have any further questions, feel free to write back. If you find any major changes that are needed in the algorithm, I'd appreciate it if you could pass them back to me. - Doctor Peterson, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/