/**
 * Test of a more storage-efficient Fibonacci number calculator that uses
 * the BigInteger type to permit computation of larger Fibonacci numbers.
 *
 * @author Wayne Eberly
 *
 */

import java.math.*;

public class Fibonacci5 {

	/**
	 * Test of a more storage-efficient Fibonacci number calculator
	 * that uses the BigInteger type to permit computation of larger
	 * Fibonacci numbers.
	 */
	public static void main(String[] args) {
		System.out.print("Test of a More Storage-Efficient Fibonacci Number ");
		System.out.println("Calculator That Uses the ");
		System.out.print("BigInteger Type to Permit the Computation ");
		System.out.println("of Larger Fibonacci Numbers");
		System.out.println("");
		for (int i=0; i <= 200; i++){
			System.out.print("n: ");
			System.out.printf("%3d", i);
			System.out.print(";     nth Fibonacci number: ");
			System.out.printf("%45s", fib(i).toString());
			System.out.println("");
		}
	}

	/**
	 * Computes a specified Fibonacci number as a BigInteger
	 * 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 BigInteger fib(int i) {
		if (i<0) {
			throw new IllegalArgumentException("Negative Input: " + i);
		} else {			// i >= 0
			if (i==0) {
				return BigInteger.ZERO;
			} else {		// i >= 1
				if (i==1) {
					return BigInteger.ONE;
				} else {	// i >= 2
					BigInteger previous = BigInteger.ZERO;
					BigInteger current = BigInteger.ONE;
					BigInteger 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.add(current);
						previous = current;
						current = next;
						assert previous.equals(sfib(j)) && current.equals(sfib(j+1));
					};
					assert current.equals(sfib(i));
					return current;
				}
			}
		}
	}

	/**
	 * Computes a specified Fibonacci number as a BigInteger 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 BigInteger sfib(int i) {
		if (i<0) {
			throw new IllegalArgumentException("Negative Input: " + i);
		} else {			// i >= 0
			if (i==0) {
				return BigInteger.ZERO;
			} else {		// i >= 1
				if (i==1) {
					return BigInteger.ONE;
				} else {	// i >= 2
					return sfib(i-1).add(sfib(i-2));
				}
			}
		}
	}

}