/*
* 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 dynamic programming version of Fibonacci_MS
//The standard Finonacci; the MS version is commented out

public class Fibonacci_MS_dynamic {
    
    /** Creates a new instance of Fibonacci_MS */
    public Fibonacci_MS_dynamic() {
    }
    
    
 
 static int count = 0;
 static long [] arrMS; 
 	public static void main (String [] args)
 	{
//  		int lim = 10000000;
  		int lim = 90;
                arrMS = new long[lim+1];
                arrMS[0] = 1;
//		for (int m = 1; m <= lim; m = 10*m)
		for (int m = 1; m <= lim; m++)
  		{
                    arrMS[m] = -1;
                }                
		for (int n = 0; n <= lim; n++)
//		for (int n = 1; n <= lim; n = 10*n)
  		{
                        count = 0;
  			long ms = MS(n);
 			System.out.print("MS(" + n + ") = " +  ms);
 			System.out.println(" count = " +  count);
                                        arrMS[0] = 1;
		for (int m = 1; m <= lim; m++)
  		{
                    arrMS[m] = -1;
                }                

		 }
	 }
 
 	public static long MS(int n)
	 {
 		count++;
	 	if (n < 0) return 0;
	 	if (n <= 1) return 1;
                if (arrMS[n] < 0) arrMS[n] =  MS(n-1) + MS(n-2);
//                if (arrMS[n] < 0) arrMS[n] =  MS(n/3) + MS(n/5);
 		return (arrMS[n]); 
 	}
 }
 

/*  Standard Fibonacci performance
init:
deps-jar:
compile-single:
run-single:
MS(0) = 1 count = 1
MS(1) = 1 count = 3
MS(2) = 2 count = 5
MS(3) = 3 count = 7
MS(4) = 5 count = 9
MS(5) = 8 count = 11
MS(6) = 13 count = 13
MS(7) = 21 count = 15
MS(8) = 34 count = 17
MS(9) = 55 count = 19
MS(10) = 89 count = 21
MS(11) = 144 count = 23
MS(12) = 233 count = 25
MS(13) = 377 count = 27
MS(14) = 610 count = 29
MS(15) = 987 count = 31
MS(16) = 1597 count = 33
MS(17) = 2584 count = 35
MS(18) = 4181 count = 37
MS(19) = 6765 count = 39
MS(20) = 10946 count = 41
MS(21) = 17711 count = 43
MS(22) = 28657 count = 45
MS(23) = 46368 count = 47
MS(24) = 75025 count = 49
MS(25) = 121393 count = 51
MS(26) = 196418 count = 53
MS(27) = 317811 count = 55
MS(28) = 514229 count = 57
MS(29) = 832040 count = 59
MS(30) = 1346269 count = 61
MS(31) = 2178309 count = 63
MS(32) = 3524578 count = 65
MS(33) = 5702887 count = 67
MS(34) = 9227465 count = 69
MS(35) = 14930352 count = 71
MS(36) = 24157817 count = 73
MS(37) = 39088169 count = 75
MS(38) = 63245986 count = 77
MS(39) = 102334155 count = 79
MS(40) = 165580141 count = 81
MS(41) = 267914296 count = 83
MS(42) = 433494437 count = 85
MS(43) = 701408733 count = 87
MS(44) = 1134903170 count = 89
MS(45) = 1836311903 count = 91
MS(46) = 2971215073 count = 93
MS(47) = 4807526976 count = 95
MS(48) = 7778742049 count = 97
MS(49) = 12586269025 count = 99
MS(50) = 20365011074 count = 101
MS(51) = 32951280099 count = 103
MS(52) = 53316291173 count = 105
MS(53) = 86267571272 count = 107
MS(54) = 139583862445 count = 109
MS(55) = 225851433717 count = 111
MS(56) = 365435296162 count = 113
MS(57) = 591286729879 count = 115
MS(58) = 956722026041 count = 117
MS(59) = 1548008755920 count = 119
MS(60) = 2504730781961 count = 121
MS(61) = 4052739537881 count = 123
MS(62) = 6557470319842 count = 125
MS(63) = 10610209857723 count = 127
MS(64) = 17167680177565 count = 129
MS(65) = 27777890035288 count = 131
MS(66) = 44945570212853 count = 133
MS(67) = 72723460248141 count = 135
MS(68) = 117669030460994 count = 137
MS(69) = 190392490709135 count = 139
MS(70) = 308061521170129 count = 141
MS(71) = 498454011879264 count = 143
MS(72) = 806515533049393 count = 145
MS(73) = 1304969544928657 count = 147
MS(74) = 2111485077978050 count = 149
MS(75) = 3416454622906707 count = 151
MS(76) = 5527939700884757 count = 153
MS(77) = 8944394323791464 count = 155
MS(78) = 14472334024676221 count = 157
MS(79) = 23416728348467685 count = 159
MS(80) = 37889062373143906 count = 161
MS(81) = 61305790721611591 count = 163
MS(82) = 99194853094755497 count = 165
MS(83) = 160500643816367088 count = 167
MS(84) = 259695496911122585 count = 169
MS(85) = 420196140727489673 count = 171
MS(86) = 679891637638612258 count = 173
MS(87) = 1100087778366101931 count = 175
MS(88) = 1779979416004714189 count = 177
MS(89) = 2880067194370816120 count = 179
MS(90) = 4660046610375530309 count = 181
BUILD SUCCESSFUL (total time: 0 seconds)
*/

/* MS Fibonacci performance
init:
deps-jar:
Compiling 1 source file to /media/disk/Files/Programs/NetBeans/BigOh_NB/fibonacci/build/classes
compile-single:
run-single:
MS(1) = 2 count = 3
MS(10) = 5 count = 9
MS(100) = 16 count = 19
MS(1000) = 49 count = 31
MS(10000) = 157 count = 51
MS(100000) = 616 count = 75
MS(1000000) = 1897 count = 109
MS(10000000) = 5843 count = 147
BUILD SUCCESSFUL (total time: 0 seconds)
 */