Assignment

Part 1

The Fibonacci sequence is defined as follows. If Fib(k) denotes the kth number in the Fibonacci sequence, then, for non-negative positions in the sequence,

Fib(1) = 1

Fib(2) = 1

Fib(n) = Fib(n-1) + Fib(n-2)

In English, we may say that a Fibonacci number is ***** sum of its two immediate predecessors, except for the first two Fibonacci numbers, which are both 1.

Implement a class called Fibonacci. This class should provide a single class method (static) with the following signature:

double Fibonacci::getNthFibonacciRecursively(int n)

which should do exactly that. It calculates and returns the nth Fibonacci number and does so recursively, by invoking itself for certain input values of n. Note that its parameter n is an integer, but its return value is a double. Why? Answer this question in a single short sentence within the header comment of this method.

From your main(), issue calls to Fibonacci for various values of n in the range 1 to 10 and make sure that the output concurs with your paper-and-pencil calculation. Handle the case for n <= 0 by returning an invalid value and note it in the documentation of the function (within comments). For example you'd say that the function will return -1 for n <= 0. That's perfectly acceptable.

Part 2

In this part of the answer you are going to profile your function. But rather than use the system profiler which was not part of this course's instruction, you will build and use a very simple measurement tool.

Windows users:

The following function returns a timestamp in milliseconds since the system started.

double getMillis() {

return (double) getTickCount();

}

To use it in your code, include the system header "WinSock2.h" as follows, immediately following your standard header declarations:

#include

The exact value returned by getMillis() doesn't matter for the purposes of this question. What matters is the difference in the return value between two successive calls to the function. If you call it at times A and B, then the difference between the two return values is the number of milliseconds elapsed. You are going to call this function to measure something about your Fibonacci function.

In your main(), you must call Fibonacci::getNthFibonacciRecursively(n) in a loop with progressively increasing values of n from 1 to 40. You must call getMillis() both immediately before and after your call for the nth Fibonacci number. E.g.

double timeStamp1 = getMillis();

Fibonacci::getNthFibonacci(n);

double timeStamp2 = getMillis();

double millisToCompute = timeStamp2 - timeStamp1;

•For each n, you must print the time taken to compute your result.

•You must study the relation between n and the time taken and predict the time it will take to calculate Fibonacci(100). It is important that you don't actually calculate the 100th Fibonacci number (especially not using your recursive function). You must simply study the time taken to calculate the first 40 numbers in the sequence and predict the time it will take to calculate the 100th number. Report this time in the most intuitive and appropriate time unit (whether it's microseconds, milliseconds, minutes or hours is up to you, but don't say it will take********** milliseconds. Convert this into a time unit humans can naturally relate to.

•You can use a method of your choice to do the prediction - Eyeballing and intuiting, plotting on a sheet of graph paper, using a spreadsheet program if you have one, or using WolframAlpha.com. For example, at wolframalpha.com, you can enter the "Exponential fit: num1, num2, num3, ..." and it will try to infer an exponential equation to calculate the numbers as a function of its position in the input sequence.