fi.c

*/

#include

#include

#include "fibonacci.h"

int *la;

int *ha;

int main(){

int i=0, n = 40;

clock_t t1, t2;

printf("**Iterative algorithm measurement** ");

ha = &i;

la = ha;

printf("iterative_fibonacci(%d):%d ", n, iterative_fibonacci(n));

printf("high address:%lu ", ha);

printf("low address:%lu ", la);

int memory_span1 = (unsigned long) ha - (unsigned long) la;

printf("iterative_fibonacci(%d) memory span:%d ", n, memory_span1);

//run time measuring for iterative_fibonacci

int m1 = 500000;

t1=clock();

for (i=0; i

iterative_fibonacci(n);

}

t2=clock();

double time_span1 = (double) t2-t1;

printf("time_span(iterative_fibonacci(%d) for %d times):%0.1f (ms) ", n, m1, time_span1);

printf(" **Recursive algorithm measurement** ");

la = ha;

printf("recursive_fibonacci(%d):%d ", n, recursive_fibonacci(n));

printf("high address:%lu ", ha);

printf("low address:%lu ", la);

int memory_span2 = (unsigned long) ha - (unsigned long) la;

printf("recursive_fibonacci(%d) memory span:%d ", n, memory_span2);

//run time measuring recursive_fibonacci

int m2 = 10;

t1=clock();

for (i=0; i

recursive_fibonacci(n);

}

t2=clock();

double time_span2 = t2-t1;

printf("time_span(recursive_fibonacci(%d) for %d times) in (ms):%0.1f ", n, m2, time_span2);

printf(" **Comparison of recursive and iterative algorithms** ");

printf("memory_span(recursive_fibonacci(%d))/memory_span(iterative_fibonacci(%d)):%0.1f ", n, n, ((double) memory_span2)/memory_span1);

printf("time_span(recursive_fibonacci(%d))/time_span(iterative_fibonacci(%d)):%0.1f ", n, n, (time_span2/time_span1)*(m1/m2));

return 0;

}

Fibonacci numbers are defined by F(1)=1, F(2)=1, F(i) = F(i-1)+F(i-2), i=2,... Write a C program, named fibonacci.h, which contains the following two functions. 1. int recursive_fibonacci(int n) which computes and returns the nth Fibonacci number f(n) using recursive algorithm (i.e., using recursive function). 2. int iterative_fibonacci(int n) which computes and returns the nth Fibonacci number f(n) using iterative algorithm (i.e., using a loop). Add global a pointer to the above functions to hold the lowest memory address of the local variables in call stack. Use the provided the main function program fibonacci main.c to compare the space and time usages of the two functions. The output should be like the following. Read and understand how the global pointers are used to measure the memory spans in call iterative_fibonacci(40) and iterative_fibonacci(40) and recursive_fibonacci(40), and how the running time spans are me and compared. Public test gcc fibonacci.h fibonacci_main.c -o fibonacci fibonacci **Iterative algorithm measurement** iterative_fibonacci (40):102334155 high address : 6422252 low address: 6422192 iterative fibonacci(40) memory span:60 time_span( iterative_fibonacci(40) for 500000 times):72.0 (ms) **Recursive algorithm measurement** recursive_fibonacci(40):102334155 high address:6422252 low address : 6420976 recursive_fibonacci(40) memory span: 1276 time_span(recursive_fibonacci(40) for 10 times) in (ms):9603.0 **Comparison of recursive and iterative algorithms** memory_span(recursive_fibonacci (40))/memory_span( iterative_fibonacci(40)):21.3 time_span(recursive_fibonacci (40))/time_span( iterative_fibonacci(40)):6668750.0 For iterative algorithm, use two variables (see class note). For recursive algorithm, use the recursion formula: F(1)=1, F(2)=1, F(i) = F(i-1) + F(i-2), n = 3, 4, ... Type your source code of fibonacci.h, refer to the following structure. fibonacci.h /* your program signature extern int *la; // global pointer variable to get local variable address int iterative_fibonacci(int n) { if (&n