Decimal To Fraction Conversion - A Simpler Version

Date: 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/