package Fibonacci2;

/**
 * Fibonacci Number Calculator.
 *
 * @author Wayne Eberly
 */

public class Fibonacci {

 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 is equal to the j-1'st Fibonacci
	 *     number
	 *  c) current is equal to 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 == SFibonacci.fib(j))
                     && (current == SFibonacci.fib(j+1));
         };
	 return current;
       }
     }
   }
 } 

}