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.
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 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, 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: [1.3]
Where the next fraction (the first being a0) is: [1.4]
That is the next fraction is a0+1/a1
, 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
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
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:
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 respectively 1,0 and 0,1.
First we will compute the values of
pk/qk= [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, p0is a0, and q0is 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: [2.6] Simplifying: =
And [2.7] Recalling: p1=(a0·a1+1) [2.4, repeated] q1=a1 [2.5, repeated] We have: [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. [2.9]
We can work out the right-hand-side: [2.10]
[2.11]
[2.12]
Rearranging: [2.13]
Finally, substituting the values of p1, p2, q1 and q2 [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: [2.8, repeated]
We replace a2 with a2+1/a3:
Multiplying throughout by a3:
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:
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
k
qk
pk
ak
-2
1
0
-1
0
1
0
1 ,[a0·q-1+q-2]
a0 ,[a0·p-1+p-2]
a0
1
a1 [a1·q0+q-1]
a0·a1+1, [a1·p0+p-1]
a1
2
a2·a1+1 , [a2·q1+q0]
a0·a1·a2+a2+a0 , [a2·p1+p0]
a2
3
a1·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: [2.19]
We can use our short-cut to compute pk+1/qk+1. [2.20]
Multiplying throughout by ak+1: [2.21]
Rearranging: [2.22]
Substituting the values for pk and qk from 2.19: [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. ■
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: