import java.io.*;

public class FibonacciNumbers
{
	public static long recursiveFibNum(int n)
	{
		if (n < 3) return 1;
		else return (recursiveFibNum(n-1) + recursiveFibNum(n-2));
	}
	
	public static long FibNum(int n)
	{
		if (n < 3) return 1;
		
		long[] fib = new long[n];
		fib[0] = fib[1] = 1;
		
		for (int i = 2; i < n; i ++)
			fib[i] = fib[i-1] + fib[i-2];
			
		return fib[n-1];
	}

	static long[] myfibs;
	public static long FibNum3(int n)
	{
		if (myfibs[n] == 0)
			myfibs[n] = FibNum3(n-1) + FibNum3(n-2);	
		
		return myfibs[n];
	}
	
	public static long FibNum4(int n)
	{
		int i;
		long[] nums = new long[3];
		nums[0] = nums[1] = 1;
		
		for (i = 2; n > 1; i = (i + 1)%3, n--)
		{
			nums[i] = nums[(i+1)%3] + nums[(i+2)%3];
		}
		
		return nums[(i-1)%3];
	}

	static BufferedReader keyboard = new BufferedReader 
										    	(new InputStreamReader (System.in));


	public static void main(String[] args) throws IOException
	{
		System.out.println("Hello.  Tell me which Fibonacci number you would like "
								+ "\nto know (1,2,3,etc).  I will tell you how long both "
								+ "\nthe recursive computation and iterative computation "
								+ "\ntook.  Enter n < 1 to quit:");
		
		long t0, t1;
		
		int n = Integer.parseInt(keyboard.readLine());
		
		myfibs = new long[1500];
		for (int i = 0; i < myfibs.length; i ++)
			myfibs[i]=0;
		myfibs[0] = myfibs[1] = myfibs[2] = 1;
		
		while (n >= 1)
		{
			t0 = System.currentTimeMillis();
			long result = FibNum(n);
			t1 = System.currentTimeMillis();		
			System.out.println("The " + n + "th Fibonacci number is " + result + ".");
			
			System.out.println("Iterative computation time: " + (((double)t1 - t0)/1000) + " seconds.");
			
			t0 = System.currentTimeMillis();
			//result = recursiveFibNum(n);
			t1 = System.currentTimeMillis();
			
			System.out.println("Recursive computation time: " + (((double)t1 - t0)/1000) + " seconds.");
		
		
			t0 = System.currentTimeMillis();
			long result2 = FibNum3(n);
			t1 = System.currentTimeMillis();
			
			System.out.println("Recursive with memory computation time: " + (((double)t1 - t0)/1000) + " seconds.");
		

			t0 = System.currentTimeMillis();
			long result3 = FibNum4(n);
			t1 = System.currentTimeMillis();
			
			System.out.println("Recursive with three mem locations: " + (((double)t1 - t0)/1000) + " seconds.");
			
			
			System.out.println("The numbers " + result2 + "  " + result3);
		





		   System.out.print("Again? : ");
			n = Integer.parseInt(keyboard.readLine());
		}
		
	}
}