Assignment 7

In this exercise, you work with rational approximations of floating point numbers. Click here in order to know about the theory of continued fractions. In order that the precision is good, work with double or long double variables. (Don't use float variables.)

Represent a finite continued fraction of the form <x₀,x₁,...,x_k-1> by a linked list. Define a structure with self-referencing pointers to represent a node in such a list.

Write a function that takes a floating point number (a double variable) x and the desired number k of terms. The function should generate a linked list storing the continued fraction expansion of x with a maximum of k terms and returns the pointer heading that list. The function may have a prototype of the following form:

   node *cfracApprox ( double x , int k ) ;

If the continued fraction expansion terminates after i terms for some i<k, then your output list should contain only i terms. Otherwise, truncate the continued fraction expansion after k terms are generated and return the list of these k terms.

Write another function that accepts as its sole argument a list holding a (finite) continued fraction expansion and prints that continued fraction in the short-hand notation described here. The prototype of this function may be as follows:

   void printCFrac ( node *head ) ;

Write a third function that generates the first, second, ..., k-th convergents from the linked list computed above. Print each such convergent both as a rational fraction and as a floating point number. Generating the i-th convergent <x₀,x₁,...,x_i-1> would require using the values x_i-1,...,x₁,x₀ in that order, i.e., in the reverse order as they are stored in the list. I leave it to your ingenuity to chalk out a strategy to handle elements in this revesre order. Using recursion might help you. Alternatively, you may think about reversing the list itself.

Finally, print all these k convergents.

Submit the output of your program on the following floating point values. Use k=12 terms in your continued fractions.

   3.14159265358979323846 (pi)
   2.7182818284590452354  (e)
   1.61803398874989484820 (golden ratio)
   3.
   3.141

The first three (in fact, four) inputs would create little difficulty. You are expected to run into trouble with the last input. The problem you would face has something to do with floating point errors. Tackle the problem gracefully (see my program's transcript on input 3.1). Learn how to live with floating point numbers.

Sample run

The following examples handle k=5 terms.

   x = 3.14159265358979323846
   Continued fraction expansion is <3,7,15,1,292>
   Convergent  1 =         3 / 1         = 3.000000000000000000.
   Convergent  2 =        22 / 7         = 3.142857142857142794.
   Convergent  3 =       333 / 106       = 3.141509433962264008.
   Convergent  4 =       355 / 113       = 3.141592920353982521.
   Convergent  5 =    103993 / 33102     = 3.141592653011902492.

   x = 3.1
   Continued fraction expansion is <3,9,1>
   Convergent  1 =         3 / 1         = 3.000000000000000000.
   Convergent  2 =        28 / 9         = 3.111111111111111160.
   Convergent  3 =        31 / 10        = 3.100000000000000089.
   Convergent  4 =        31 / 10        = 3.100000000000000089.
   Convergent  5 =        31 / 10        = 3.100000000000000089.

---

[Submission site] [Lab home] [Course home]