Instructions for Java Assignment: Please use the FibonacciDemo.java file (shown
ID: 3690482 • Letter: I
Question
Instructions for Java Assignment:
Please use the FibonacciDemo.java file (shown below) as your starting point. You will be implementing several more ways of calculating the Fibonacci sequence. This will allow you to test your work by ensuring that the same results are calculated by each of the methods.
I have included two possible ways to perform the Fibonacci sequence - the classic recursive strategy, and the iterative strategy. If you would like to understand how the sequence is calculated, I recommend you uncomment the println's and see how the same results are calculated numerous times. You can add additional println's to understand it better if you wish.
Implementing a Memoized Recursive Method:
For the recursive method, note how many times that the method is called. This number will increase very quickly as the ssize increases! This is one of the main reasons that it is so slow. However, one of the reasons that the method is called so many times is that the same value must be recalculated numerous times. For example, let's assume we're calculating the eight Fibonacci number. We end up calculating, say, Fib(4) several times. What if we just stored that value instead of re-calculating it? We'd save numerous method calls (since every call to Fib(4) means 9 recursive method calls) and would probably see faster results.
This process of saving return values in case they are needed again is called "memoization". In some languages, this is available as part of the language (e.g., Clojure's memoize function). In Java, however, we must implement it ourselves. This is usually done by adding some sort of data structure in which these values can be looked up. If the value exists, then it can just be returned instead of continuing to calculate the result.
Think how you would do this, and implement the memoizedRecursiveFibonacci() method. Remember to also have it increment the _numMemoizedCalls variable each time it is called. Afterwards, uncomment the println() that displays the number of calls. You will be pleasantly surprised at how many fewer calls are necessary with a properly memoized method!
The trade-off: this will also cause more memory usage, since you will need to store each of these calculated values somewhere.
Implementing a Closed-Form Method:
Could we make calculating even more efficient than a memoized or iterative method? It turns out that the Fibonacci sequence is closely related to the Golden Ratio (phi). This value, which is equal to approximately 1.6180339887..., is seen often in various mathematical functions.
Instead of calculating via recursion or looping, we can simply calculate it in what's called a "closed-form" manner, that is, simply solving an equation. The _n_th Fibonacci number is equal to:
If you round this number to the nearest integer, it is equal to the nth Fibonacci number!
Think how you would implement this, and implement it as the closedFormFibonacci() method.
The trade-off: since we are now using floating-point numbers, we may have to worry about floating-point errors for large values. You don't have to worry about these for this lab, but be aware that they exist.
Implementing a Lookup Table Method:
The Fibonacci sequence is not going to change. It has been calculated numerous times (many times by students in Intermediate Java classes before you). The fifth Fibonacci number will always be 5, and the twentieth will always be 6765. Why are we even bothering to calculate them again?
In fact, we don't have to do so! We could just store them in a large array and call the nth element of the array. You can get the array of precalculated Fibonacci numbers and the nth element will be the nth Fibonacci number.
Implement the lookupTableFibonacci() method. You can use the FibNums.txt file to seed the array for this (just go ahead and copy and paste it).
The downside: if the number isn't stored in the array (there's a finite size to all precalculated arrays), then we're going to have to calculate it anyways.
Final Analysis:
After you have completed all of these implementations, you can time them (comment out all but one of the calls, and run with a reasonably-sized Fibonacci value, say 45; try this for each of the different methods). This can be done as follows on a Linux or OS X system:
You are interested in the time marked "real". If you want to know about the other kinds of time when it comes to testing performance of an application, you can learn about them in CS1632!
On Windows machines, you should be able to use PowerShell to do this in a similar manner (although caveat lector, I do not own a Windows machine and have not tried this!)
Check how long the calculation takes with different implementations. See how the results differ when calculating small values and large values.
FibonacciDemo.java:
public class FibonacciDemo {
private static long _numCalls = 0;
private static long _numMemoizedCalls = 0;
// The Fibonacci Sequence is the series of numbers found by starting
// with 0, 1, 1.. and the next number is the sum of the previous two numbers.
// For example, 0 + 1 = 1, so the next number in the Fibonacci sequence is 1.
// 1 + 1 is 2, so the third number is 2. 2 + 1 is 3, so the fourth number is 3.
// etc. - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, etc.
// This can very easily be calculated recursively. For the nth number, if n
// is 1, then return 1. Otherwise, return whatever the results of the
// last two elements of the Fibonacci sequence are, by calling the Fibonacci
// method again.
public static long recursiveFibonacci(long num) {
_numCalls++;
if (num <= 1) {
// BASE CASE
System.out.println("Fib(" + num + ") = " + num);
return num;
} else {
// RECURSIVE CASE
long num1 = recursiveFibonacci(num - 1);
long num2 = recursiveFibonacci(num - 2);
System.out.println("Fib(" + num + ") = " + num1 + " + " + num2);
return num1 + num2;
}
}
public static long iterativeFibonacci(long num) {
// This method does the same thing as the recursive method
// in RecursionDemo!
long back2 = 0;
long back1 = 1;
long current = 1;
for (long j=1; j < num; j++) {
current = back2 + back1;
back2 = back1;
back1 = current;
}
return current;
}
public static long memoizedFibonacci(long num) {
return -1;
}
public static long closedFormFibonacci(long num) {
return -1;
}
public static long lookupTableFibonacci(long num) {
return -1;
}
public static void main(String[] args) {
int num = -1;
if (args.length >= 1) {
num = Integer.parseInt(args[0]);
if (num <= 0) {
printErrorAndDie();
}
} else {
printErrorAndDie();
}
long fib1, fib2, fib3, fib4;
System.out.println("Recursive Fib(" + num + ") = " + recursiveFibonacci(num));
System.out.println(" Took " + _numCalls + " recursive calls!");
System.out.println("Iterative Fib(" + num + ") = " + iterativeFibonacci(num));
// System.out.println("Memoized Recursive Fib(" + num + ") = " + memoizedFibonacci(num));
// System.out.println(" Took " + _numMemoizedCalls + " recursive calls!");
// System.out.println("Closed-Form Fib(" + num + ") = " + closedFormFibonacci(num));
// System.out.println("Lookup Table Fib(" + num + ") = " + lookupTableFibonacci(num));
}
// Print error message and end program
public static void printErrorAndDie() {
System.out.println("Program requires one argument, a positive integer.");
System.exit(1);
}
}
Explanation / Answer
import static java.lang.Math.pow;
import java.io.File;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.*;
public class FibonacciDemo {
private static long _numCalls = 0;
private static long _numMemoizedCalls = 0;
private static long[] dictionary;
private static double phi = 1.6180339887;
private static long[] fibArray;
// The Fibonacci Sequence is the series of numbers found by starting
// with 0, 1, 1.. and the next number is the sum of the previous two numbers.
// For example, 0 + 1 = 1, so the next number in the Fibonacci sequence is 1.
// 1 + 1 is 2, so the third number is 2. 2 + 1 is 3, so the fourth number is 3.
// etc. - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, etc.
// This can very easily be calculated recursively. For the nth number, if n
// is 1, then return 1. Otherwise, return whatever the results of the
// last two elements of the Fibonacci sequence are, by calling the Fibonacci
// method again.
public static long recursiveFibonacci(long num) {
_numCalls++;
if (num <= 1) {
// BASE CASE
System.out.println("Fib(" + num + ") = " + num);
return num;
} else {
// RECURSIVE CASE
long num1 = recursiveFibonacci(num - 1);
long num2 = recursiveFibonacci(num - 2);
System.out.println("Fib(" + num + ") = " + num1 + " + " + num2);
return num1 + num2;
}
}
public static long iterativeFibonacci(long num) {
// This method does the same thing as the recursive method
// in RecursionDemo!
long back2 = 0;
long back1 = 1;
long current = 1;
for (long j=1; j < num; j++) {
current = back2 + back1;
back2 = back1;
back1 = current;
}
return current;
}
public static long memoizedFibonacci(int num) { // Changed the long num to int num
_numMemoizedCalls++;
if (dictionary == null) {
dictionary = new long[num];
}
if (dictionary[num - 1] == 0) {
if (num == 1) {
dictionary[num - 1] = 1;
} else if (num <= 2) {
dictionary[num - 1] = num - 1;
} else {
dictionary[num - 1] = memoizedFibonacci(num - 1) + memoizedFibonacci(num - 2);
}
}
return dictionary[num - 1];
}
public static long closedFormFibonacci(long num) {
double squareRoot = Math.sqrt(5);
double res = pow(phi,num)/squareRoot;
// System.out.println(squareRoot +" :: "+ res + " :: "+ (int) res + " :: "+ (int)Math.round(res));
return (int)Math.round(res);
}
public static int lookupTableFibonacci(int num) throws IOException{
//I have written the functionality there is some minor exception is coming which could be easily resolved.
// I couln't complete it because of lack of time.
// Scanner scanner = new Scanner(new File("FibNums.txt"));
// int [] array = new int [1000];
// int i = 0;
// while(scanner.hasNextInt()){
// array[i++] = scanner.nextInt();
// }
// if (array.length <= num){
// return array[num-1];
// } else {
// return lookupTableFibonacci(num - 1) + lookupTableFibonacci(num - 2);
// }
return -1;
}
public static void main(String[] args) throws IOException{
int num = -1;
if (args.length >= 1) {
num = Integer.parseInt(args[0]);
if (num <= 0) {
printErrorAndDie();
}
} else {
printErrorAndDie();
}
// BufferedReader br=new BufferedReader (new FileReader ("FibNums.txt"))
// while(br.readLine()!=null){
// System.out.println(li)
// }
long fib1, fib2, fib3, fib4;
System.out.println("Recursive Fib(" + num + ") = " + recursiveFibonacci(num));
System.out.println(" Took " + _numCalls + " recursive calls!");
System.out.println("Iterative Fib(" + num + ") = " + iterativeFibonacci(num));
System.out.println("Memoized Recursive Fib(" + num + ") = " + memoizedFibonacci(num));
System.out.println(" Took " + _numMemoizedCalls + " recursive calls!");
System.out.println("Closed-Form Fib(" + num + ") = " + closedFormFibonacci(num));
// System.out.println("Lookup Table Fib(" + num + ") = " + lookupTableFibonacci(num));
}
// Print error message and end program
public static void printErrorAndDie() {
System.out.println("Program requires one argument, a positive integer.");
System.exit(1);
}
}