Description

Lab05. Continued Fractions
In mathematics, any real number, x, can be represented by a continued fraction as the following
(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, … ].
The sequence can be finite or infinite. If the sequence is infinite, let (5.2)
xk = [ a0; b1, a1, …, bk, ak ],
| 2k integers{z }
Thus, (5.3)
(5.4)
(5.5)
(5.6)
(5.7)
. (5.8)
And,
lim xk = x.
k→∞
Using continued fractions, the square root of any integer, x, can be expressed as (5.9)
. (5.10)
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.
(5.12)
2k integers 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

The following table shows the approximations up to k = 10.
Table 1. Continued fraction approximation for √2.

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
| q (x) − qk 1(x)| ≤ 10−9. (5.14) k −
assuming qk(x) is the approximate value of √x.
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.
*/
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.