Description
In mathematics, any real number, x, can be represented by a continued fraction as the following
x = a0 +
b1
a1 +
b2
a2 +
b3
a3 +
b4
· · ·
(5.1)
where ai
, bi are integers. As a shorthand representation, we write the above equation as a sequence
x = [ a0; b1, a1, b2, a2, b3, a3, . . . ]. (5.2)
The sequence can be finite or infinite. If the sequence is infinite, let
xk = [ a0; b1, a1, . . . , bk, ak
| {z }
2k integers
], (5.3)
Thus,
x0 = a0, (5.4)
x1 = a0 +
b1
a1
, (5.5)
x2 = a0 +
b1
a1 +
b2
a2
, (5.6)
x3 = a0 +
b1
a1 +
b2
a2 +
b3
a3
, (5.7)
x4 = a0 +
b1
a1 +
b2
a2 +
b3
a3 +
b4
a4
. (5.8)
And,
lim
k→∞
xk = x. (5.9)
Using continued fractions, the square root of any integer, x, can be expressed as
√
x = 1 +
x − 1
2 +
x − 1
2 +
x − 1
2 + · · ·
. (5.10)
1
Or, in sequence notation
√
x = [ 1; x − 1, 2, x − 1, 2, x − 1, 2, . . . ] (5.11)
Since this is an infinite sequence, the value can only be approximated by a finite sequence in computer
evaluation.
√
x ≈ qk(x) = [ 1; x − 1, 2, x − 1, 2, x − 1, 2, . . . , x − 1, 2,
| {z }
2k integers
] (5.12)
In this case, the error exists and is
εk = qk(x) −
√
x. (5.13)
For example, x = 2,
√
2 can be approximated by the following sequence
q0(2) = 1
ε0 = 1 −
√
2 = −0.414214
q1(2) = 1 +
1
2
= 1.5
ε1 = 1.5 −
√
2 = 0.0857864
q2(2) = 1 +
1
2 +
1
2
= 1.4
ε2 = 1.4 −
√
2 = −0.0142136
q3(2) = 1 +
1
2 +
1
2 +
1
2
= 1.41667
ε3 = 1.41667 −
√
2 = 0.0024531
The following table shows the approximations up to k = 10.
Table 1. Continued fraction approximation for √
2.
k qk εk
0 1 -0.414214
1 1.5 0.0857864
2 1.4 -0.0142136
3 1.41667 0.0024531
4 1.41379 -0.000420459
5 1.41429 7.21519e-05
6 1.4142 -1.23789e-05
7 1.41422 2.1239e-06
8 1.41421 -3.64404e-07
9 1.41421 6.25218e-08
10 1.41421 -1.0727e-08
In this assignment, you need to write a C program to find the approximate values of √
2,
√
11,
√
121, √
1221,
√
12321,
√
123321,
√
1234321, and √
12344321, using continued fraction (Equation 5.10) with small
errors. To ensure a small error is obtained, your program should check for
| qk (x) − qk−1(x)| ≤ 10−9
. (5.14)
assuming qk(x) is the approximate value of √
x.
2
Example output of the program is
$ ./a.out
x sqrt(x)
2 1.414213562
11 xxxxxxxxxxx
121 11.000000000
1221 xxxxxxxxxxxx
12321 111.000000000
123321 xxxxxxxxxxxxx
1234321 1111.000000000
12344321 xxxxxxxxxxxxxx
Notes.
1. Create a directory lab05 and use it as the working directory.
2. Name your program source file as lab05.c.
3. The first few lines of your program should be comments as the following.
/* EE231002 Lab05. Continued Fractions
ID, Name
Date:
*/
4. After finishing editing your source file, you can execute the following command to compile it,
$ gcc lab05.c
If no compilation errors, the executable file, a.out, should be generated, and you can execute it by
typing
$ ./a.out
5. After you finish verifying your program, you can submit your source code by
$ ∼ee231002/bin/submit lab05 lab05.c
If you see a ”submitted successfully” message, then you are done. In case you want to check which
file and at what time you submitted your labs, you can type in the following command:
$ ∼ee231002/bin/subrec
It will show the last few submission records.
6. You should try to write the program as efficient as possible. The format of your program should be
compact and easy to understand. These are part of the grading criteria.
