# Ken Ward's Mathematics Pages

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

Number Theory Contents

## 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 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:
[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.
  qk pk ak rk 1/rk Current Error Valid    k Fraction Table 1 Remarks 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 0 1 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 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 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 4 7 1 0.3643 1.3643 1.7500000000 0.0179000000 yes 11 19 2 0.7450 2.7450 1.7272727273 0.0048272727 yes 15 26 1 0.3423 1.3423 1.7333333333 0.0012333333 yes 41 71 2 0.9214 2.9214 1.7317073171 0.0003926829 yes 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:
k qk pk ak rk Table 2 -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, 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:
[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.

Number Theory Contents

Ken Ward's Mathematics Pages

# Faster Arithmetic - by Ken Ward

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: