Using Continued Fractions to Convert Decimals to Fractions

Example | Discussion | TI-81 program | Commented TI-86 program

---

Approximate the decimal with a "continued fraction".  If the continued fraction terminates, we can easily simplify it into a simple fraction.  If the continued fraction nearly terminates, we'll hope we're close.  As in all calculator/computer algorithms, knowing what is "close enough" is often more art than science.

Next, drop the integer part of the previous reciprocal (the "2") and take the reciprocal again: , so .  Putting this into the old expression for x, we get: 
Repeating the process again, . Combining, we get , and the process has terminated -- the last reciprocal was an integer, so we cannot take the reciprocal of its decimal part.  Finally, we can simplify the fraction starting at the bottom: .

Of course, the calculator doesn't exercise such judgement - it blindly follows some algorithm.  Most of the process in the example above is mechanical, though - lop off the part to the left of the decimal point, take the reciprocal of what's left, and repeat.  Where some judgement might be called for is in deciding when to quit.

The process terminates if some step results in an integer.  If the result of a step is close to an integer, we might guess the difference is just roundoff error.  In the last example, depending on your calculator, instead of 18.33333333, you might get 18.3333333336, and the next step could give 0.333333333587  instead of 0.33333333, leading to 2.99999999772 instead of "3" as the last reciprocal.  To automate the process, we need some objective criterion to indicate when we should round.

A simple criterion to program into the calculator is to round if a reciprocal is within some small distance from an integer, e.g. rounding 2.99999999772 to 3. The TI-81 program below rounds if a reciprocal is within 0.00001 of an integer.

Because of these approximations above, when this process gives a fraction, the only thing we know for sure is that the fraction is close to our original decimal.  For example, on a TI-86, both .486725663717 and .486725663716 get converted to 55/113, even though those can't both be right.

There is one additional "stopping criterion": If the process takes too long, give up.  After any step, simply dropping the decimal part will give a fraction f close to our original number x, and the dropped decimal part is related to the difference |x-f|.  Remember, though, that we only know x to about 10-12 decimal places.  After many steps, the difference |x-f| might be smaller than a digit in the 14th decimal place.  Since the calculator doesn't know what those digits of x are (but treats them as zero), there is already more error in our process than dropping that decimal part would cause.  If the last result isn't close to an integer, we're not particularly convinced that x has a simple rational representation, and probably shouldn't report our approximate results, unless we indicate they are approximate.  In the TI-81 program below, if the process doesn't terminate in 20 steps, the program gives up and returns the decimal x.  One good practice that the program below doesn't follow is to check the work against the original decimal and throw out the results if there is too much disagreement.

As noted above,  we can get some nice rational approximations by stopping short - something neither the TI-82/85/86 nor the program below does.  For example, after 3 steps, we get , which is accurate to six decimal places.

The other TI calculators have a [>FRAC] button built-in.  Note that this algorithm works equally well for negative decimals.  A small tweak was added to remove the initial integer part for numbers of magnitude greater than 1. The program will halt if it exceeds 20 iterations.  Also, the final reciprocal is deemed an integer if it differs from an integer by at most 1E-5.  These criteria are arbitrary, but seem to give good results.

Bonus for people interested in the program itself:

:Ans->X        'The last screen result is our number; store in X
:If X==int X:Then:
:Disp X,"over",1:Stop:End
               'Added to catch integer inputs (otherwise we divide by 0).

:1->dimL S     'The list S will store our sequence of denominators
:X->Temp       'Make a temporary copy of X to work on.
:1->C          'C counts iterations of main procedure

:While(abs (Temp-Int Temp)>1E-5)(C<=20)
               'The main procedure continues for 20 iterations, or until
               'Temp is "very nearly" an integer, whatever comes first.

    :Int Temp->S(C)
               'The integer part of Temp is our next denominator (except on
               'the first iteration, when this is just the integer part of X).
    :Temp-S(C)->Temp
               'Take decimal part of Temp (note results when Temp<0!)
    :Temp^-1->Temp
               'Take the reciprocal of the decimal part.
    :C+1->C    'Increment iteration counter
:End           'End of main procedure. Now C=total # iterations.
:IntTemp->S(C) 'Store the last, hopefully integer, value of Temp.
:If C>20:Then
:Disp x:Stop:End
               'If we took more than 20 iterations, results are dubious,
               'return just the original value of X.

               'Now it's time to reconstruct the rational number from the
               'entries in the partial fraction.

:1->N          'N is our numerator-to-be
:S(C)->D       'D is our denominator-to-be, start with last denominator.
:For(K,C-1,2,-1)
               'K goes from C-1 down to 2, we "work backward" through our
               'sequence of denominators
    :D*S(K)+N->T
               'T holds our next value for the numerator
    :D->N
    :T->D      'Taking reciprocals, numerator and denominator are exchanged.
:End
:N+D*S(1)->N   'Remember S(1) holds the original integer part of X
:If abs((N/D)/X-1)<1E-7:Then
               '(added)If N/D agrees w/ X to about 7 places...
:Disp N,"OVER",D
               '...display numerator and denominator
:Else:Disp X
               'or else if agreement is bad, just return X again.

Notes:

1. To use: Get the desired number on the screen as the result of whatever operation, then immediately run the program.
2. I've added two error traps:  One catches integer inputs (which would be silly, but which crash the original program with a division-by-zero error).  The other compares the final output with the original input as a double-check.
3. The 20-iterations limit is probably generous.  I suspect that if more than 10 iterations are made, roundoff error has taken over and our results will be lousy anyway.
4. Note this works just fine on negative inputs, though the sequences of S's isn't really obvious.
5. Even if the program refuses to give a fraction (and returns your value of X), looking at S is instructive - it gives a continued fraction approximately equal to X.
6. To see these approximate fractions, remove the ":If C>20:Then:Disp x:Stop:End" in the middle of the program, and cut the iteration limit down to around 10. Then one always gets a result - even in the approximate cases.  The results are pretty impressive (try it on Pi or root(2)).