nav.gif (1245 bytes)mathematics

Ken Ward's Mathematics Pages

Number Theory Continued Fractions: Converting A Decimal to A Fraction Using An Algorithm.

Number Theory Contents

Page Contents

  1. Computing Terms of Continued Fraction and Current Fraction At the Same Time
    1. Example when the integral part of the fraction is not zero
    2. Example when the integral part of the fraction is zero
  2. Proof
    1. k=0
    2. k=1
    3. k=2
    4. k=3
    5. Short-Cut Method
    6. Deciding on the Initial p's and q's
    7. Summary so far
    8. Proof by Induction




Computing Terms of Continued Fraction and Current Fraction At the Same Time

This approach is similar to the approach using Euclid's Algorith, but is more suited to converting decimals to fractions.
We seek to find the continued fraction representation for 1.7321, which is √3 to 4 places. Following convention, the numerator is p, the denonimator, q, a is the term of the continued fraction, and r is the remaining fraction. 1/r is the reciprocal of r, and makes the new a and r values. The Fraction is the current value of the continued fraction. The error is the comparison of the actual decimal, 1.7321, and the current fraction, p/q.

The table is set up for k=-2 and -1, setting the q and p values as 1, 0 and 0, 1. These values are always the same for any continued fraction.

a0 is the integer part of the fraction, and is naturally 0, when the decimal is less than 1.

Example when the integral part of the fraction is not zero

The values of a are computed by at first taking the integer value of the original decimal, in this case the integer value of 1.7321. We make a note of the remainder, r0, 0.7321. We take the reciprocal of r0, which is 1.3659, and a1 is the integral part, 1, and the new remainder, r1, is 0.3659. We repeat the process calculating the a's.
We find the q's and p's using:
qk=ak·qk-1+qk-2  [1.1]
pk=ak·pk-1+pk-2  [1.2]
For k>=0

We compute the current fraction from the recurrence:
cf21.gif [1.3]
Where the next fraction (the first being a0) is:
cf22.gif [1.4]

That is the next fraction is a0+1/a1 , and so on.

Of course,
cf23.gif [1.5]

Table 1, below, gives an example using 1.7321, and Table 2 shows what we might normally write down.
Table 1
     k qk pk ak rk 1/rk Current Fraction Error Valid
 Remarks
-2  1 0




 
 We first set up the table by writing the values for p and q when k=-2 and k=-1. That is, 1,0 and 0, 1
-1  0 1
 
  
  
  
  
  
0 1 1 1 0.7321 1.7321


We can either compute all the a's and then compute the q's and p's, or do both together (Just a preference. I like to compute the a's first). At first we simply make a0 equal to the integer part of the decimal. So because the original decimal is 1.7321, a0=1.
We then compute the p's and q's as follows:
q0=a0·q-1+q-2  =1·0+1=1
p0=a0·p-1+p-2  =1·1+0=1
1 1 2 1 0.3659 1.3659 2.0000000000 0.2679000000 yes q1=a1·q0+q-1  =1·1+0=1
p1=a1·p0+p-1  =1·1+1=2
2 3 5 2 0.7330 2.7330 1.6666666667 0.0654333333 yes q2=a2·q1+q0  =2·1+1=3
p2=a2·p1+p0  =2·2+1=5
3 4 7 1 0.3643 1.3643 1.7500000000 0.0179000000 yes
4 11 19 2 0.7450 2.7450 1.7272727273 0.0048272727 yes
5 15 26 1 0.3423 1.3423 1.7333333333 0.0012333333 yes
6 41 71 2 0.9214 2.9214 1.7317073171 0.0003926829 yes
7 56 97 1 0.0853 1.0853 1.7321428571 0.0000428571 no As the error is less than 0.00005, which, if we consider the decimal to be accurate to 4 places, means the actual error is less than the expected error, so this and any further results are questionable.

The continued fraction for 1.7321=[1,1,2,1,2,1,2], considering the original number accurate to 4 decimal places.

Table 2 is what me might actually write down, when computing the continued fraction for 1.7321:
 Table 2
k qk pk ak rk
-2 1 0  
  
-1 0 1  
  
0 1 1 1 0.7321
1 1 2 1 0.3659
2 3 5 2 0.7330
3 4 7 1 0.3643
4 11 19 2 0.7450
5 15 26 1 0.3423
6 41 71 2 0.9214
7 56 97 1 0.0853

Example when the integral part of the fraction is zero

In Table 3 we use the algorithm when the integral part of the decimal is zero. The example is to seek the continued fraction for 0.7647.

Table 3
k q p a r Number Fraction ErrorRemarks
-2 1 0




-1 0 1




0 1 0 0 0.7647 0.7647

1 1 1 1 0.3077 1.3077 1.0000000000 0.7321000000
2 4 3 3 0.2499 3.2499 0.7500000000 0.9821000000
3 17 13 4 0.0016 4.0016 0.7647058824 0.9673941176
4 10629 8128 625 0.0000 625.0000 0.7647003481 0.9673996519We end here because  the remainder is zero, and the computation is exact.
The continued fraction is [0,1,3,4]

Proof

We wish to show that we can compute the current fraction, p/q, for a continued fraction, using the following:
qk=ak·qk-1+qk-2  [1.1, repeated]
pk=ak·pk-1+pk-2  [1.2, repeated]
For k>=0

We wish also to show that the values for k=-2 and k=-1 are repectively 1,0 and 0,1.

First we will compute the values of
pk/qk=cf23.gif [1.5, repeated]
in a step by step manner, beginning with k=0.

So we calculate the fraction as far as k, in each step.

k=0

The first result, when k=0, is
p0/q0=a0   [2.1]
We take p0=a0, and q0=1
Because p0 and q0 are relatively prime, p0 is a0, and q0 is 1, because this is the simplest form.

Alternatively, we note:
p0/q0=a0/1
p0·1−q0·a0=0
According to Euclid's Algorithm, we can find integers, p0 and q0, which are relatively prime. The simplest solution is
p0=a0 [2.2.1]
q0=1  [2.2.2]

k=1

When k=1, we have:
p1/q1=a0+1/a1  [2.2]
=(a0·a1+1)/a1  [2.3]

Therefore:
p1=(a0·a1+1) [2.4]
q1=a1            [2.5]

k=2

When k=2, we have:
cf31.gif [2.6]
Simplifying:
=cf32.gif  

cf33.gif
And
cf34.gif [2.7]
Recalling:
p1=(a0·a1+1) [2.4, repeated]
q1=a1            [2.5, repeated]
We have:
cf35.gif [2.8]
Which expresses p2 and q2 in terms of the previous q's and p's, suggesting:
qk=ak·qk-1+qk-2  
pk=ak·pk-1+pk-2  

k=3

While the algebra was quite straightforward, as k becomes greater, the algebra becomes more and more involved. We will work out the fraction for k=3 as usual, and then mention an easier method.
 cf323.gif [2.9]

We can work out the right-hand-side:
cf36.gif [2.10]

cf37.gif [2.11]

cf38.gif [2.12]

Rearranging:
cf39.gif [2.13]

Finally, substituting the values of p1, p2, q1 and q2
cf310.gif [2.14]
Once again, this suggests:
qk=ak·qk-1+qk-2  
pk=ak·pk-1+pk-2  

Short-Cut Method

The short-cut method of computing the current fraction in a continued fraction is based on the definition of continued fractions and the recursion formula.

Assuming we have evaluated a previous fraction, say for k=2, and we have:
cf35.gif [2.8, repeated]

We replace a2 with a2+1/a3:
cf311.gif

Multiplying throughout by a3:
cf312.gif

Rearranging:
cf313.gif

Substituting the previous p values:
cf14.gif
And we have our formula.
For the sake of clarification, using the short-cut does not presume the truth of the formula we are seeking to prove. The short-cut could be applied to the convolution of a's, or to any continued fraction. The q's and the p's have been defined and determined in terms of the a's and the method is simply a way to work out the next fraction, provided we know the previous one.
■

Deciding on the Initial p's and q's

It seems, that for k>=2, the following recursions apply:
qk=ak·qk-1+qk-2  
pk=ak·pk-1+pk-2  

While we have not yet proved it, we can examine the results for k=0 and k=1, and decide on the values required for pk-2, pk-1, qk-2, qk-1.

When k=1, according to our formula, we have:
p1=a1·p0+p-1
We know:
p1=(a0·a1+1) [2.4, repeated], and
p0=a0 [2.2.1, repeated]
So:
p1=(a0·a1+1)=a1·p0+p-1 =a1·a0+p-1
Therefore,
p-1=1 [2.15]
Similarly,
q1=a1·q0+q-1
We know:
q1=a1            [2.5, repeated]
q0=1  [2.2.2, repeated]
a1 =a1·1+q-1
So, q-1=0 [2.16]
When k=0,
According to our formula:
p0=a0·p-1+p-2
We know:
p-1=1 [2.15, repeated]
p0=a0 [2.2.1, repeated]
a0=a0·1+p-2
So:
p-2=0 [2.17]

In the same fashion, we can find
q-2=1 [2.18]
■

Summary so far

So far we note that we can use our formulae:
qk=ak·qk-1+qk-2  
pk=ak·pk-1+pk-2  
for k>=0 and k<=3
kqkpkak
-210
-101
01 ,[a0·q-1+q-2]a0 ,[a0·p-1+p-2]a0
1a1 [a1·q0+q-1]a0·a1+1, [a1·p0+p-1]a1
2a2·a1+1 , [a2·q1+q0]a0·a1·a2+a2+a0 , [a2·p1+p0]a2
3a1·a2·a3+a3+a1,  [a3·q2+q1]a0·a1·a2·a3+a2·a3+a0·a3+a0·a1+1,  [a3·p2+p1]a3

What we will next attempt is to prove through mathematical induction, that the formula is generally true for k>=0.

Proof by Induction

We wish to prove the following formulae: qk=ak·qk-1+qk-2  
pk=ak·pk-1+pk-2  

We have shown the formula is correct for k=0 (and k=1, 2 and 3).

We assume it is correct for k=k. So we assume:
cf41.gif [2.19]

We can use our short-cut to compute pk+1/qk+1.
cf42.gif [2.20]

Multiplying throughout by ak+1:
cf43.gif [2.21]

Rearranging:
cf44.gif [2.22]

Substituting the values for pk and qk from 2.19:
cf45.gif [2.23]

That is, we find we have the same result predicted by our formula. Therefore, if it is true for k, it is true for k+1.

So, if the formula works for a value k>=0, then it works for the next value. It works for k=0, so it works for all k.
■







Number Theory Contents

Ken Ward's Mathematics Pages