숙제 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.
페이지 내역: 1, 마지막 수정: 01 Nov 2015 09:50