숙제 01

For the problems below, you need to write programs using C language. Turn in your own source programs written independently (by email) together with reports.

1.

The Fibonacci sequences satisfy the following recurrence relation

(1)
\begin{align} F_n = F_{n-1} + F_{n-2} , \quad n \ge 2, \end{align}

with $F_0 = 0$ and $F_1 = 1$. Suppose that you wrote the following program to calculate the sum of frst 20 Fibonacci numbers $F_0, F_1, \cdots, F_{20}$, but it does not work correclty.

  • (a) Compile and run the program below. What is the output?
  • (b) Fix the code in order to obtain the intended output? What is it?
#include <stdio.h>
#define N 20
 
int main(void)
{
    int i, j, k;
    int p;
 
    k = 0;                    /* F[0] */
    j = 1;                    /* F[1] */
 
    int total = k + j;
    for(p = 2; p < N; p++){
        i = j + k;            /* F[n] = F[n-1] + F[n-2] */
        int total = total + i;
        k = j;
        j = i;
    }
    printf(" Total: %5d\n", total);
    return 0;
}

2.

Write a (short) program to find the machine epsilon of your computer, using C language, in both single and double precision. Run your program to obtain the outputs.

3.

This problem is to show that you need to be carreful to avoid unstable algorithms in which roundoff errors can increase exponentially.
The “golden mean”, $\phi$, is given by $\phi = ( \sqrt{5} - 1)/2 \simeq 0.61803398875 \cdots$,

  • (a) Write a C progam to calcualte the $n$-th power of $\phi$, using successive multiplications
(2)
\begin{align} \phi^0 = 1, \quad \mathrm{and} \quad \phi^n = \phi \cdot \phi^{n-1} \quad \mathrm{for} \quad n = 1, 2, 3, \cdots, \end{align}
­
and plot $\phi^n$ as a function of $n$ for $0 \le n \le 50$. (The ordinate should be in lograithmic scale.)
  • (b) Another (clever) way to calculate $\phi^n$ is to use following recursion relation
(3)
\begin{align} \phi^{n+1} = \phi^{n-1} - \phi^n \quad \mathrm{for} \quad n = 1, 2, 3, \cdots, \end{align}
­
Show that Equation (3) is equivalent to Equation (2). Use Equation (3) to calcualte $\phi^n$ in both single and double precision for $0 \le n \le 50$. Compare the results with those in part (a) by overploting all the results in the same figure.
  • (c) Why do you think are the results in parts (a) and (b) so different for high $n$? (Hint: there is another solution of Equation (3) whose magnitude is greater than unity.)

4.

Evaluate

(4)
\begin{align} S_n = \sum_{j=1}^n {{1} \over {j(j+1)}}, \end{align}

using your computer for arbitrary $n= 10, 10^2, 10^4$, and $10^6$ by using the method below. Comment on the answers obtained.

  • (a) By summing the terms from the largest terms first to the smallest terms last.
  • (b) By summing the terms from the smallest terms first to the largest terms last.
  • (c) Using the Kahan summation formula.