/*
 * Fibonacci_MS.java
 *
 * Created on February 13, 2008, 12:26 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

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

/* MS Fibonacci performance
 
bash-2.03$ java Fibonacci_MS 1000000000
MS(1) = 2 count = 3
MS(10) = 5 count = 12
MS(100) = 16 count = 43
MS(1000) = 49 count = 140
MS(10000) = 157 count = 453
MS(100000) = 616 count = 1684
MS(1000000) = 1897 count = 5477
MS(10000000) = 5843 count = 17162
MS(100000000) = 19344 count = 55849
MS(1000000000) = 73242 count = 202332

*/