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.
: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: