Hi, I need help with the following assignment -The different algorithms for comp
ID: 3707043 • Letter: H
Question
Hi, I need help with the following assignment
-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 today’s 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 program’s 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. Then, you will implement another class called TimeFibonacci to measure the time of calculating a Fibonacci number N. 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.
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");
}
}
---------------------------------------------------------------------------------------
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;
}
}
Explanation / Answer
Here is the program and output,
Please note that using a fabonacci with just for loop (simple one) will not show the significant diffrence with N=45
therefore to explain the problem and show the output i have used recursive fabonacci function. for the reference i have added commented implementation of fabonacci using for loop
import java.util.*;
import java.io.*;
/**
* Time how long it takes to compute fibonacci numbers.
*/
public class TimeFibonacci
{
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
System.out.println("What is the value of n?");
System.out.println("Please enter an integer value greater than or equal to 0");
//int n = in.nextInt();
int n = 45;
timeBasic(n);
}
public static void timeBasic(int n)
{
System.out.println("TIMING BASIC RECURSIVE FIBONACCI");
RecursiveFibonacci fab = new RecursiveFibonacci();
Calendar start = Calendar.getInstance();
int N = fab.fibonacci(n);
System.out.println(N);
Calendar end = Calendar.getInstance();
long diff = end.getTime().getTime() - start.getTime().getTime();
System.out.println("Time to compute ... was "+ diff + " milliseconds.");
}
};
class RecursiveFibonacci
{
/**
* basic - The simple version of fibonacci.
*
* @param n A positive integer.
* @return The nth fibonacci number.
*/
/*int fibonacci(int n){
int prev=0, next=1, result=0;
for (int i = 0; i < n; i++) {
result=prev+next;
prev=next;
next=result;
}
return result;
}*/
public int fibonacci(int n) {
if(n == 0)
return 0;
else if(n == 1)
return 1;
else
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
Here is the on two dry run with number N=45
1. output
2. output
output 3
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.