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 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₀ 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, r₀, 0.7321. We take the reciprocal of r₀, which is 1.3659, and a₁ is the integral part, 1, and the new remainder, r₁, 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₀) is:
[1.4]

That is the next fraction is a₀+1/a₁ , 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:
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₀/q₀=a₀   [2.1]
We take p₀=a₀, and q₀=1
Because p₀ and q₀ are relatively prime, p₀ is a₀, and q₀ is 1, because this is the simplest form.

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

k=1

When k=1, we have:
p₁/q₁=a₀+1/a₁  [2.2]
=(a₀·a₁+1)/a₁  [2.3]

Therefore:
p₁=(a₀·a₁+1) [2.4]
q₁=a₁            [2.5]

k=2

When k=2, we have:
[2.6]
Simplifying:
=  


And
[2.7]
Recalling:
p₁=(a₀·a₁+1) [2.4, repeated]
q₁=a₁            [2.5, repeated]
We have:
[2.8]
Which expresses p₂ and q₂ 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₁, p₂, q₁ and q₂
[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₂ with a₂+1/a₃:


Multiplying throughout by a₃:


Rearranging:


Substituting the previous p values:

And we have our formula.
■

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₁=a₁·p₀+p_-1
We know:
p₁=(a₀·a₁+1) [2.4, repeated], and
p₀=a₀ [2.2.1, repeated]
So:
p₁=(a₀·a₁+1)=a₁·p₀+p_-1 =a₁·a₀+p_-1
Therefore,
p_-1=1 [2.15]
Similarly,
q₁=a₁·q₀+q_-1
We know:
q₁=a₁            [2.5, repeated]
q₀=1  [2.2.2, repeated]
a₁ =a₁·1+q_-1
So, q_-1=0 [2.16]
When k=0,
According to our formula:
p₀=a₀·p_-1+p_-2
We know:
p_-1=1 [2.15, repeated]
p₀=a₀ [2.2.1, repeated]
a₀=a₀·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

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: q_k=a_k·q_k-1+q_k-2  
p_k=a_k·p_k-1+p_k-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 p_k+1/q_k+1.
[2.20]

Multiplying throughout by a_k+1:
[2.21]

Rearranging:
[2.22]

Substituting the values for p_k and q_k 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.
■







Number Theory Contents

Ken Ward's Mathematics Pages

---

---

Faster Arithmetic - by Ken Ward