The different algorithms for computing Fibonacci numbers will be timed in this programming assignment. This introduces a number of complications. To find the time, the following chunk of code will be used.

Calendar start = Calendar.getInstance();

// The Code being timed goes here

Calendar end = Calendar.getInstance();

long diff = end.getTime().getTime() - start.getTime().getTime();

System.out.println("Time to compute ... was "+ diff + " milliseconds.");

Each time the getInstance() method is invoked, the current system time will be retrieved. That time is the number of milliseconds from some fixed date. One consequence of this is that the difference may be off by as much as a millisecond. Any time of that order is not to be trusted. With the speed of todays computers, some algorithms may complete well within that time frame. To address this issue, the code that is being timed may be inside a for loop that will execute the code multiple times. The reported time will be divided by the number of times the loop executed. This, of course, will introduce an extra bit of time for the loop overhead, but it is assumed that this will be small and can therefore be ignored.

Our timing difficulties are further complicated by the fact that the code being timed may not have been running the whole time. The Java Runtime Environment (JRE) is not the only program being executed. As the load on the computer changes, the amount of time the program gets will change as well. Running the same timing code with the same parameters will not give you the same result. You hope that the results are within 10%, but there is no guarantee. Another complicating factor is that the JRE is threaded. (Multiple tasks can be running each in their own thread within the JRE.) Some development environments will have threads running that will compete with your programs thread for time.

Another issue is that as computers get faster, the time required for the execution of an implementation of an algorithm will decrease. This presents some problems in applications. An appropriate number of times to execute a loop today may be insufficient tomorrow. Some strategies have been used to ameliorate these problems. For example, a system can guarantee that enough iterations are done to get a reasonable execution time (usually on the order of a minute or so). The code is timed once for a fixed number of iterations. That time is then used to determine the number of iterations to use for the subsequent tests.

In this assignment, you need to implement a RecursiveFibonacci class (10 pt). Then, you will implement another class called TimeFibonacci to measure the time of calculating a Fibonacci number N (15 pt). Starting code of both classes are provided. To test your code, run N=45 more than 2 times and upload a screenshot of the result like the example below. You need to upload both your code and your test result for this assignment. Submission failed to meet the submission requirement will not be graded. Grade may be forfeited.

public class RecursiveFibonacci

{

/**

* basic - The simple version of fibonacci.

*

* @param n A positive integer.

* @return The nth fibonacci number.

*/

public long basic(long n)

{

long result = 1;

return result;

}

}

import java.util.*;

import java.io.*;

/**

* Time how long it takes to compute fibonacci numbers.

*/

public class TimeFibonacci

{

public static void main(String args[])

{

System.out.println("What is the value of n?");

int n = getInt("Please enter an integer value greater than or

equal to 0");

timeBasic(n);

}

public static void timeBasic(int n)

{

System.out.println("TIMING BASIC RECURSIVE FIBONACCI");

}

}

Lis-MacBook-Pro:Test LLIUS java TimeFibonacci What is the value of n? Please enter an integer value greater than or equal to 0 45 TIMING BASIC RECURSIVE FIBONACCI Time to compute fibonacci (45) using basic recursion was 5160 milliseconds. Lis-MacBook-Pro:Test LLIUS java TimeFibonacci What is the value of n? Please enter an integer value greater than or equal to0 45 TIMING BASIC RECURSIVE FIBONACCI Time to compute fibonacci (45) using basic recursion was 5201 milliseconds