I have two java program Fibonacci and ImprovedFibonacci 1 problem: I am trying a
ID: 3675421 • Letter: I
Question
I have two java program Fibonacci and ImprovedFibonacci
1 problem: I am trying add timer to both program and trying to see which one is faster. But the timer on Fibonacci is not working( Its the same timer code from ImprovedFibonacci )
2 problem: How two of the program compare with each other? And why one is faster than another?
import java.util.Scanner;
public class ComputeFibonacci {
/** Main method */
public static void main(String[] args) {
// Create a Scanner
Scanner input = new Scanner(System.in);
System.out.print("Enter an index for a Fibonacci number: ");
int index = input.nextInt();
long start = System.currentTimeMillis();
// Find and display the Fibonacci number
System.out.println("The Fibonacci number at index "
+ index + " is " + fib(index));
System.out.printf("Time: %d ms ", System.currentTimeMillis() - start);
}
/** The method for finding the Fibonacci number */
public static long fib(long index) {
if (index == 0) // Base case
return 0;
else if (index == 1) // Base case
return 1;
else // Reduction and recursive calls
return fib(index - 1) + fib(index - 2);
}
}
import java.util.Scanner;
public class ImprovedFibonacci {
/** Main method */
public static void main(String args[]) {
// Create a Scanner
Scanner input = new Scanner(System.in);
System.out.print("Enter an index for the Fibonacci number: ");
int index = input.nextInt();
long start = System.currentTimeMillis();
// Find and display the Fibonacci number
System.out.println(
"Fibonacci number at index " + index + " is " + fib(index));
System.out.printf("Time: %d ms ", System.currentTimeMillis() - start);
}
/** The method for finding the Fibonacci number */
public static long fib(long n) {
long f0 = 0; // For fib(0)
long f1 = 1; // For fib(1)
long f2 = 1; // For fib(2)
if (n == 0)
return f0;
else if (n == 1)
return f1;
else if (n == 2)
return f2;
for (int i = 3; i <= n; i++) {
f0 = f1;
f1 = f2;
f2 = f0 + f1;
}
return f2;
}
}
Explanation / Answer
1).
Hi, for smaller input , you can some not see much difference. Try big value like 50, 80, 100 etc.
2).
Your first program is recursive:
recursive program for Fibonacci Numbers, there are many subproblems which are solved again and again.
/* simple recursive program for Fibonacci numbers */
int fib(int n)
{
if ( n <= 1 )
return n;
return fib(n-1) + fib(n-2);
}
Run on IDE
Recursion tree for execution of fib(5)
fib(5)
/
fib(4) fib(3)
/ /
fib(3) fib(2) fib(2) fib(1)
/ / /
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/
fib(1) fib(0)
We can see that the function f(3) is being called 2 times. If we would have stored the value of f(3), then instead of computing it again, we would have reused the old stored value.
So, you can easily see that first program is computing same value again and agian. So it will take more time.
But in seconf program we are computing each fibonnacci value only once and we store in f1 and f2 variable, so that we can use to compute next fibonnacci number in constant time.