Loop and Recursive Fibonacci Function:

C++

Write two functions to compute Fibonacci numbers: one using a loop, and the other recursive as described in class. We want to compute the largest Fibonacci Numbers that we can, so we will use unsigned 64-bit integers, which take us up to 2⁶⁴ 1. Some compilers accept unsigned long long int but in Visual Studio C++ we say unsigned __int64 with a double underscore. The two prototypes are:

unsigned __int64 fibonacci_loop(int);

unsigned __int64 fibonacci_recursive(int);

We expect the recursive version to be slower for large integers, much slower than the loop version. Measure the time required to perform these computations with the following code:

#include

clock_t start, finish;

double elapsedTime;

start = clock();

// do something here that requires lots of time

finish = clock();

elapsedTime = (finish - start)/CLOCKS_PER_SEC;

cout << Time required = << elapsedTime << " seconds " << endl;

How much time is required to compute the following Fibonacci numbers using a loop?

n = 10 time required: ___________

n = 50 time required: ___________

n = 90 time required: ___________

Whats the largest Fibonacci Number we can contain in an unsigned 64-bit integer?

How much time is required to compute the following Fibonacci numbers using recursion?

n = 30 result = __________ time required: ___________

n = 35 result = __________ time required: ___________

n = 36 result = __________ time required: ___________

n = 37 result = __________ time required: ___________

n = 38 result = __________ time required: ___________

n = 39 result = __________ time required: ___________

n = 40 result = __________ time required: ___________

n = 41 result = __________ time required: ___________

n = 42 result = __________ time required: ___________

n = 43 result = __________ time required: ___________

n = 44 result = __________ time required: ___________

n = 45 result = __________ time required: ___________

n = 46 result = __________ time required: ___________

n = 47 result = __________ time required: ___________

n = 48 result = __________ time required: ___________

n = 49 result = __________ time required: ___________

n = 50 result = __________ time required: ___________

Determine the largest values of n for which the corresponding Fibonacci Numbers can be computed within the given time.

n = _____ time required: less than 10 seconds

n = _____ time required: less than 30 seconds

n = _____ time required: less than 1 minute

n = _____ time required: less than 5 minutes

Estimate the value of n for the largest value of fib(n) that can be computed using recursion in one hour on your computer. Explain in detail how you estimated this value. Also describe any additional data you took to arrive at this value. Attach any additional work required.

n = ______ for time = 1 hour (3600 seconds)

Repeat this problem for the largest value of n for which the corresponding Fibonacci Number can be computed (using our simple recursive algorithm) for the following times.

n = ______ for time = 1 day (86,400 seconds)

n = ______ for time = 1 week (604,800 seconds)

n = ______ for time = 1 year (31,558,149.8 seconds)

n = ______ for time = 1 century (100 years)

n = ______ for time = 1 millennium (ten centuries)

n = ______ for time = 10,000 years (time span of human civilization)

n = ______ for time = 1 million years (time that homo sapiens has existed, more or less)

n = ______ for time = 5 billion years (time that the Earth has existed)

n = ______ for time = 15 billion years (time that the Universe has existed)

As part of your homework, answer all of the above questions. Show your work. Hint there are plenty of good math packages out there that will fit an exponential curve to your data and allow you to compute these predictions.

What is memoization?

Can we improve the performance of our recursive computation using memoization?

Use the memorized version of your program to compute the largest Fibonacci Number that can be handled by the unsigned __int64 data type.

Rank:

Value:

The only operation required to compute Fibonacci Numbers is addition, and we have taken our Big Integer code that far. Compute the following Fibonacci Numbers using our Big Integer type:

100:

200:

300:

400:

500:

1000:

Loop and Recursive Factorial Function: Name __________________

Use the same timer techniques as described on the previous page.

The two prototypes are

unsigned __int64 factorial_loop(int);

unsigned __int64 factorial_recursive(int);

Determine the largest input value n for which a factorial can be computed.

What was the largest result for factorial using unsigned int? n = ______________

n! = ______________

What was the elapsed time computing this factorial using loops? t = ______________

What is the elapsed time computing this factorial using recursion? t = ______________

Are these times significantly different? Why or why not? Answer in the space below: