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 denominator, 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.
a_{0} 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 aare
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, r_{0},
0.7321. We take the reciprocal of r_{0}, which is
1.3659, and a_{1} is the integral part, 1, and the
new remainder, r_{1}, is 0.3659. We repeat the
process calculating the a's.
We find the q's and p's using:
q_{k}=a_{k}·q_{k-1}+q_{k-2}
[1.1]
p_{k}=a_{k}·p_{k-1}+p_{k-2}
[1.2]
For k>=0
We compute the current fraction from the recurrence:
[1.3]
Where the next fraction (the first being a_{0}) is:
[1.4]
That is the next fraction is a_{0}+1/a_{1}
, and so on.
Of course,
[1.5]
Table 1, below, gives an example using 1.7321, and Table 2 shows what we might
normally write down.
Table 1
k
q_{k}
p_{k}
a_{k}
r_{k}
1/r_{k}
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 a_{0}
equal to the integer part of the decimal. So because the original
decimal is 1.7321, a_{0}=1.
We then compute the p's and q's as follows:
q_{0}=a_{0}·q_{-1}+q_{-2}
=1·0+1=1
p_{0}=a_{0}·p_{-1}+p_{-2}
=1·1+0=1
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
q_{k}
p_{k}
a_{k}
r_{k}
-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
Error
Remarks
-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.9673996519
We 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:
q_{k}=a_{k}·q_{k-1}+q_{k-2}
[1.1, repeated]
p_{k}=a_{k}·p_{k-1}+p_{k-2}
[1.2, repeated]
For k>=0
We wish also to show that the values for k=-2 and k=-1 are respectively 1,0 and 0,1.
First we will compute the values of
p_{k}/q_{k}= [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 p_{0}/q_{0}=a_{0} [2.1] We take p_{0}=a_{0}, and q_{0}=1 Because p_{0} and q_{0} are relatively prime, p_{0}is a_{0}, and q_{0}is 1, because this is the simplest form.
Alternatively, we note: p_{0}/q_{0}=a_{0}/1 p_{0}·1−q_{0}·a_{0}=0 According to Euclid's Algorithm, we can find integers, p_{0} and q_{0}, which are relatively prime. The simplest solution is p_{0}=a_{0} [2.2.1] q_{0}=1 [2.2.2]_{}
k=1
When k=1, we have: p_{1}/q_{1}=a_{0}+1/a_{1} [2.2] =(a_{0}·a_{1}+1)/a_{1} [2.3] _{}Therefore:_{}p_{1}=(a_{0}·a_{1}+1) [2.4] q_{1}=a_{1 } [2.5]
k=2
When k=2, we have: [2.6] Simplifying: =
And [2.7] Recalling: p_{1}=(a_{0}·a_{1}+1) [2.4, repeated] q_{1}=a_{1 } [2.5, repeated] We have: [2.8] Which expresses p_{2} and q_{2} in terms of the previous q's and p's, suggesting:
q_{k}=a_{k}·q_{k-1}+q_{k-2}
p_{k}=a_{k}·p_{k-1}+p_{k-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. [2.9]
We can work out the right-hand-side: [2.10]
[2.11]
[2.12]
Rearranging: [2.13]
Finally, substituting the values of p_{1}, p_{2}, q_{1} and q_{2} [2.14] Once again, this suggests:
q_{k}=a_{k}·q_{k-1}+q_{k-2}
p_{k}=a_{k}·p_{k-1}+p_{k-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: [2.8, repeated]
We replace a_{2} with a_{2}+1/a_{3}:
Multiplying throughout by a_{3}:
Rearranging:
Substituting the previous p values:
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:
q_{k}=a_{k}·q_{k-1}+q_{k-2}
p_{k}=a_{k}·p_{k-1}+p_{k-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 p_{k-2}, p_{k-1}, q_{k-2}, q_{k-1}.
When k=1, according to our formula, we have: p_{1}=a_{1}·p_{0}+p_{-1} We know: p_{1}=(a_{0}·a_{1}+1) [2.4, repeated], and p_{0}=a_{0} [2.2.1, repeated] So: p_{1}=(a_{0}·a_{1}+1)=a_{1}·p_{0}+p_{-1} =a_{1}·a_{0}+p_{-1} Therefore, p_{-1}=1 [2.15] Similarly, q_{1}=a_{1}·q_{0}+q_{-1} We know: q_{1}=a_{1 } [2.5, repeated] q_{0}=1 [2.2.2, repeated]
a_{1 }=a_{1}·1+q_{-1}
So, q_{-1}=0 [2.16] When k=0, According to our formula: p_{0}=a_{0}·p_{-1}+p_{-2} We know: p_{-1}=1 [2.15, repeated] p_{0}=a_{0} [2.2.1, repeated] a_{0}=a_{0}·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:
q_{k}=a_{k}·q_{k-1}+q_{k-2}
p_{k}=a_{k}·p_{k-1}+p_{k-2} for k>=0 and k<=3
Ken's book is packed with examples and explanations that enable you to discover more than 150 techniques to speed up your arithmetic and increase your understanding of numbers. Paperback and Kindle: