/*
* 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
 */


//The standard Finonacci; the MS version is commented out

public class Fibonacci_MS {
    
    /** Creates a new instance of Fibonacci_MS */
    public Fibonacci_MS() {
    }
    
    
 
 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;
// 		return (MS(n/3) + MS(n/5));
 		return (MS(n-1) + MS(n-2));
 	}
 }
 
/* Standard Fibonacci performance
init:
deps-jar:
compile-single:
run-single:
MS(0) = 1 count = 1
MS(1) = 1 count = 1
MS(2) = 2 count = 3
MS(3) = 3 count = 5
MS(4) = 5 count = 9
MS(5) = 8 count = 15
MS(6) = 13 count = 25
MS(7) = 21 count = 41
MS(8) = 34 count = 67
MS(9) = 55 count = 109
MS(10) = 89 count = 177
MS(11) = 144 count = 287
MS(12) = 233 count = 465
MS(13) = 377 count = 753
MS(14) = 610 count = 1219
MS(15) = 987 count = 1973
MS(16) = 1597 count = 3193
MS(17) = 2584 count = 5167
MS(18) = 4181 count = 8361
MS(19) = 6765 count = 13529
MS(20) = 10946 count = 21891
MS(21) = 17711 count = 35421
MS(22) = 28657 count = 57313
MS(23) = 46368 count = 92735
MS(24) = 75025 count = 150049
MS(25) = 121393 count = 242785
MS(26) = 196418 count = 392835
MS(27) = 317811 count = 635621
MS(28) = 514229 count = 1028457
MS(29) = 832040 count = 1664079
MS(30) = 1346269 count = 2692537
MS(31) = 2178309 count = 4356617
MS(32) = 3524578 count = 7049155
MS(33) = 5702887 count = 11405773
MS(34) = 9227465 count = 18454929
MS(35) = 14930352 count = 29860703
MS(36) = 24157817 count = 48315633
MS(37) = 39088169 count = 78176337
MS(38) = 63245986 count = 126491971
MS(39) = 102334155 count = 204668309
MS(40) = 165580141 count = 331160281
BUILD SUCCESSFUL (total time: 3 seconds)
*/

/* MS Fibonacci performance
 
bash-2.03$ java Fibonacci_MS 1000000000
MS(1) = 1 count = 1
MS(10) = 4 count = 7
MS(100) = 12 count = 23
MS(1000) = 37 count = 73
MS(10000) = 114 count = 227
MS(100000) = 358 count = 715
MS(1000000) = 1431 count = 2861
MS(10000000) = 4410 count = 8819
MS(100000000) = 13582 count = 27163
MS(1000000000) = 43904 count = 87807
BUILD SUCCESSFUL (total time: 0 seconds)

*/