/**
 * Test of a more storage-efficient Fibonacci number calculator.
 *
 * @author Wayne Eberly
 *
 */

public class Fibonacci3 {

	/**
	 * Test of a more storage-efficient Fibonacci number calculator.
	 */
	public static void main(String[] args) {
		System.out.println("Test of a More Storage-Efficient Fibonacci Number Calculator");
		System.out.println("");
		for (int i=0; i <= 40; i++){
			System.out.print("n: ");
			System.out.printf("%2d", i);
			System.out.print(";     nth Fibonacci number: ");
			System.out.printf("%10d", fib(i));
			System.out.println("");
		}
	}

	/**
	 * Computes a specified Fibonacci number as a long integer
	 * iteratively, using a set of three variables to store and reuse values
	 * as needed.
	 * 
	 * <p>
	 *  <strong>Precondition:</strong>
	 *       <code>i</code> is a nonnegative integer.<br />
	 *  <strong>Postcondition:</strong>
	 *       Value returned is the <code>i</code><sup>th</sup>
	 *       Fibonacci number.
	 * </p>
	 * 
	 * @param i Index of the Fibonacci number to be calculated
	 * @return The ith Fibonacci number
	 * @throws IllegalArgumentException If the input integer is negative
	 * 
	 */
	public static long fib(int i) {
		if (i<0) {
			throw new IllegalArgumentException("Negative Input: " + i);
		} else {			// i >= 0
			if (i==0){
				return 0;
			} else {		// i >= 1
				if (i==1){
					return 1;
				} else {	// i >= 2
					long previous = 0;
					long current = 1;
					long next;
					for (int j=1; j < i; j++) {
					/*
					* Loop Invariant:
					*  a) j is an integer such that 1 <= j <= i-1
					*  b) previous == sfib(j-1), the j-1'st Fibonacci
					*     number
					*  c) current == sfib(j), the j'th Fibonacci number
					* Loop Variant: i-j
					*/
						next = previous + current;
						previous = current;
						current = next;
						assert (previous == sfib(j)) && (current == sfib(j+1));
					};
					return current;
				}
			}
		}
	} 

	/**
	 * Computes a specified Fibonacci number as a long integer by a direct
	 * application of the recursive definition.
	 * 
	 * <p>
	 *  <strong>Precondition:</strong>
	 *       <code>i</code> is a nonnegative integer.<br />
	 *  <strong>Postcondition:</strong>
	 *       Value returned is the <code>i</code><sup>th</sup>
	 *       Fibonacci number.
	 * </p>
	 * 
	 * @param i Index of the Fibonacci number to be calculated
	 * @return  The ith Fibonacci number
	 * @throws IllegalArgumentException If the input integer is negative
	 *
	 */
	 public static long sfib(int i) {
		 if (i<0) {
			 throw new IllegalArgumentException("Negative Input: " + i);
		 } else {			// i >= 0
			 if (i==0) {
				 return 0;
			 } else {		// i >= 1
				 if (i==1) {
					 return 1;
				 } else {	// i >= 2
					 return sfib(i-1) + sfib(i-2);
				 }
			 }
		 }
	 }

}