/* Class: COP3530
 * Date: Jan 20, 2006
 * Instructor: Arup Guha
 * TA: Adam Campbell
 *
 * Recitation #2, Problem #2
 **/

import java.math.BigInteger;

public class Rec2Prob2{

	/* I have main throw exception so I don't need the try/catch blocks everywhere when reading in from the file.
	 * In general, this is not good programming practice, but for these simple problems we are more interested in the
	 *   algorithm.
	 **/
	public static void main(String[] args) throws Exception{

		long startTime, totalTime;
		double averageTime;
		int nValueIterMax = 200; // different values of n that we use for Iterative function
		int nValueRecurMax = 35; // different values of n that are used for the Recursive function
		int numIterIters = 100000; // number of times we run each iterative function
		int numRecurIters = 20; // number of times we run each recursive function

		System.out.println("Iterative Fibonacci:");
		System.out.println("n  time");

		// loop through all of the values of n
		for(int n = 0; n < nValueIterMax; n++){

			// obtain the time the algorithm started running
			startTime = System.currentTimeMillis();

			// Because the Iterative function is so fast, we may not get a correct time
			//   if we just run the function once.  But, if we run the function 100000 times
			//   and then divide the total time by 100000, we can get a good estimation of the
			//   time it took to run one run of the algorithm.
			for(int iter = 0; iter < numIterIters; iter++){
				Rec2Prob2.fibIterative(n);
			}

			totalTime = System.currentTimeMillis() - startTime;

			averageTime = (double)totalTime / numIterIters;

			System.out.println(n + " " + averageTime);

		}

		System.out.println();
		System.out.println("Recursive Fibonacci:");
		System.out.println("n  time");

		// loop through all of the values of n
		for(int n = 0; n < nValueRecurMax; n++){

			// obtain the time the algorithm started running
			startTime = System.currentTimeMillis();

			for(int iter = 0; iter < numRecurIters; iter++){
				Rec2Prob2.fibRecursive(n);
			}

			totalTime = System.currentTimeMillis() - startTime;

			averageTime = (double)totalTime / numRecurIters;

			System.out.println(n + " " + averageTime);

		}

	}

	// iteratively computes the nth Fibonacci number
	private static BigInteger fibIterative(int n){

		if(n == 0) return new BigInteger("0");
		if(n == 1) return new BigInteger("1");

		BigInteger[] array = new BigInteger[n+1];

		array[0] = new BigInteger("0");
		array[1] = new BigInteger("1");

		for(int i = 2; i < array.length; i++){
			array[i] = array[i-1].add(array[i-2]);
		}

		return array[n];

	}

	// recursively computes the nth Fibonacci number
	private static BigInteger fibRecursive(int n){

		if(n == 0) return new BigInteger("0");
		if(n == 1 || n == 2) return new BigInteger("1");

		return Rec2Prob2.fibRecursive(n-1).add(Rec2Prob2.fibRecursive(n-2));

	}

}