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

public class Fibonacci4 {

	/**
	* Class to report numerical overflow.
	*/
	
	public static class NumericalOverflowException extends Exception {
		/**
		* Construct a NumericalOverflowException with the
		* specified message.
                *
		* @param message The message
		*/
		NumericalOverflowException(String message) {
			super(message);
		}
	}

	/**
	 * Test of a more storage-efficient Fibonacci number calculator.
	 * <p>
	 * 
	 * @param args
	 */
	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 <= 99; i++){
			try {
				long v = fib(i);
				System.out.print("n: ");
				System.out.printf("%2d", i);
				System.out.print(";     nth Fibonacci number: ");
				System.out.printf("%21d", fib(i));
				System.out.println("");
			} catch (NumericalOverflowException ex) {
				System.out.println("");
				System.out.print("Remaining values are too large to be represented ");
				System.out.println("using Java\'s long data type.");
				break;
			};
		}
	}

	/**
	 * 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
	 * @throws NumericalOverflowException if the output is too large to be
	 *         represented using Java's long data type
	 * 
	 */
	public static long fib(int i) throws NumericalOverflowException {
		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;
						if (current < previous) {	// Check for numerical overflow
							throw new NumericalOverflowException("Overflow when computing the " + j+1 +"th Fibonacci number");
						};
						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);
				 }
			 }
		 }
	 }

}