Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Fibonacci numbers are defined as F(1)=1, F(2)=1, F(i) = F(i-1)+F(i-2), i=2, Write a C program, named fibonacci.h, containing the following two functions. 1- int recursive_fibonacci(int

Fibonacci numbers are defined as F(1)=1, F(2)=1, F(i) = F(i-1)+F(i-2), i=2,

Write a C program, named fibonacci.h, containing 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 a global 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. Note that values iterative_fibonacci(40) and recursive_fibonacci(40) should be the same as in the public test. Address and time span values will be different.

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 measured and compared.

Public test

command: gcc fibonacci_main.c -o fibonacci command: fibonacci 40 iterative_fibonacci(40):102334155 recursive_fibonacci(40):102334155 command: fibonacci **Iterative algorithm measurement** iterative_fibonacci(40):102334155 high address:6422260 low address:6422208 iterative_fibonacci(40) memory span:52 time_span(iterative_fibonacci(40) for 500000 times):86.0 (ms) **Recursive algorithm measurement** recursive_fibonacci(40):102334155 high address:6422260 low address:6420992 recursive_fibonacci(40) memory span:1268 time_span(recursive_fibonacci(40) for 10 times) in (ms):10789.0 **Comparison of recursive and iterative algorithms** memory_span(recursive_fibonacci(40))/memory_span(iterative_fibonacci(40)):24.4 time_span(recursive_fibonacci(40))/time_span(iterative_fibonacci(40)):6272674.4 

fibonacci_main.c:

*/ #include #include #include "fibonacci.h"

int *la; int *ha;

int main(int argc, char *argv[]){ int i=0, n = 40; clock_t t1, t2; if (argc > 1 ) { sscanf(argv[1], "%d", &n); printf("iterative_fibonacci(%d):%d ", n, iterative_fibonacci(n)); printf("recursive_fibonacci(%d):%d ", n, recursive_fibonacci(n)); } else {

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< m1; 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

fibonacci.h:

/* * your program signature */ #ifndef FIBONACCI_H #define FIBONACCI_H extern int *la; // global pointer variable to hold lowest variable address int recursive_fibonacci(int n) { if (&n < la) la = &n; // your implementation of the recursive algorithm } int iterative_fibonacci(int n) { if (&n < la) la = &n; // your implementation of the iterative algorithm } #endif

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Practical Database Programming With Visual Basic.NET

Authors: Ying Bai

1st Edition

0521712351, 978-0521712354

More Books

Students also viewed these Databases questions