Associated Topics || Dr. Math Home || Search Dr. Math

### Decimal To Fraction Conversion - A Simpler Version

```Date: 11/25/2002 at 04:06:24
From: Paul Bearne
Subject: Decimal To Fraction Conversion

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/
```
Associated Topics:
High School Calculators, Computers
Middle School Fractions

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search