/*
* The Fibonacci sequence is 1, 1, 2, 3, ...
* 
* (Here is more on the subject:
* http://mathworld.wolfram.com/FibonacciNumber.html )
*
* In this program, the first element of the above sequence is MS(0)
* (in the standard version), 
* following the commonly accepted convention in computer science and 
* mathematical logic that the he smallest natural number is 0.
*
* Should one assert, like it is common in math, that the smallest 
* natural number is 1, instead, then the first element of the above
* sequence becomes MS(1) and the argument of MS needs to be 
* shifted by 1.
*/



package fibonacci;

/**
 *
 * @author suchenek
 */
public class Fibonacci_iterative 
{
   /** Creates a new instance of Fibonacci_MS */
    public Fibonacci_iterative() {
    }
    
    
 
 static int count = 0;

 	public static void main (String [] args)
 	{
//  		int lim = 1000000000;
  		int lim = 40;
//                        Integer.parseInt(args[0]);
//		for (int n = 1; n <= lim; n = 10*n)
		for (int n = 0; n <= lim; n++)
  		{
                        count = 0;
  			int m = MS(n);
 			System.out.print("MS(" + n + ") = " +  m);
 			System.out.println(" count = " +  count);
		 }
	 }
 
 	public static int MS(int n)
	 {
 		count++;
	 	if (n < 0) return 0;
                if (n <= 1) return 1;
                int fib1 = 1;
                int fib2 = 1;
                int fib3 = 2;
                for (int i = 2; i < n; i++)
                {
 		count++;
                    fib1 = fib2;
                    fib2 = fib3;
                    fib3 = fib2 + fib1;
                }
                    
 		return fib3; 
 	}

}
/* Standard Fibonacci performance
init:
deps-jar:
compile-single:
run-single:
MS(0) = 1 count = 1
MS(1) = 1 count = 1
MS(2) = 2 count = 1
MS(3) = 3 count = 2
MS(4) = 5 count = 3
MS(5) = 8 count = 4
MS(6) = 13 count = 5
MS(7) = 21 count = 6
MS(8) = 34 count = 7
MS(9) = 55 count = 8
MS(10) = 89 count = 9
MS(11) = 144 count = 10
MS(12) = 233 count = 11
MS(13) = 377 count = 12
MS(14) = 610 count = 13
MS(15) = 987 count = 14
MS(16) = 1597 count = 15
MS(17) = 2584 count = 16
MS(18) = 4181 count = 17
MS(19) = 6765 count = 18
MS(20) = 10946 count = 19
MS(21) = 17711 count = 20
MS(22) = 28657 count = 21
MS(23) = 46368 count = 22
MS(24) = 75025 count = 23
MS(25) = 121393 count = 24
MS(26) = 196418 count = 25
MS(27) = 317811 count = 26
MS(28) = 514229 count = 27
MS(29) = 832040 count = 28
MS(30) = 1346269 count = 29
MS(31) = 2178309 count = 30
MS(32) = 3524578 count = 31
MS(33) = 5702887 count = 32
MS(34) = 9227465 count = 33
MS(35) = 14930352 count = 34
MS(36) = 24157817 count = 35
MS(37) = 39088169 count = 36
MS(38) = 63245986 count = 37
MS(39) = 102334155 count = 38
MS(40) = 165580141 count = 39
BUILD SUCCESSFUL (total time: 0 seconds) */