There are many situations where we want to approximate a real number by a rational number. For example, we can approximate by But is a slightly better approximation, and it is more efficient in the sense that it uses a smaller denominator than The method of continued fractions is a procedure that yields this type of good approximations. In this section, we summarize some basic facts. For proofs and more details, see, for example, [Hardy-Wright], [Niven et al.], [Rosen], and [KraftW].
An easy way to approximate a real number is to take the largest integer less than or equal to This is often denoted by For example, If we want to get a better approximation, we need to look at the remaining fractional part. For this is This looks close to One way to express this is to look at We can approximate this last number by and therefore conclude that 1/7 is indeed a good approximation for and that is a good approximation for Continuing in this manner yields even better approximations. For example, the next step is to compute and then take the greatest integer to get 15 (yes, 16 is closer, but the algorithm corrects for this in the next step). We now have
If we continue one more step, we obtain
This last approximation is very accurate:
This procedure works for arbitrary real numbers. Start with a real number Let and Then (if otherwise, stop) define
We obtain the approximations
We have therefore produced a sequence of rational numbers It can be shown that each rational number gives a better approximation to than any of the preceding rational numbers with Moreover, the following holds.
If for integers then for some
For example, and
Continued fractions yield a convenient way to recognize rational numbers from their decimal expansions. For example, suppose we encounter the decimal 3.764705882 and we suspect that it is the beginning of the decimal expansion of a rational number with small denominator. The first few terms of the continued fraction are
The fact that 9803921 is large indicates that the preceding approximation is quite good, so we calculate
which agrees with all of the terms of the original 3.764605882. Therefore, is a likely candidate for the answer. Note that if we had included the 9803921, we would have obtained a fraction that also agrees with the original decimal expansion but has a significantly larger denominator.
Now let’s apply the procedure to We have
This yields the numbers
Note that the numbers 1, 9, 246, 1, 4 are the quotients obtained during the computation of in Subsection 3.1.3 (see Exercise 49).
Calculating the fractions such as
can become tiresome when done in the straightforward way. Fortunately, there is a faster method. Define
Then
Using these relations, we can compute the partial quotients from the previous ones, rather than having to start a new computation every time a new is found.