//clockFib.c  -- by tsaiwn@csie.nctu.edu.tw
//test using clock( ) function through calling Fibonacci
//====== 電腦很快, 但是若要做的事情很多很多, 還是會感覺很慢 !
// clock( ) 與 time( ) 都宣告在 <time.h>
// 請看看K&R課本附錄 B.10 並仔細研究這程式, 請用很多 n 值測試, 並寫心得!
// 注意課本上寫說 difftime( )是以秒為單位是錯的! 它仍是以 tick 為單位!
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
//Fibonacci Rabbit problem:
// 第0個月有一對小兔子, 每月會長大, 大兔每月會生出一對, 請問第n月有幾對?
long long fib(int n) {  // recursive version, very SLOW !
   if(n<0) return 0;   // 以前沒有肚子
   if(n<2) return 1;   // 第 0個月一對小兔子, 第 1 個月一對大兔子
   return fib(n-1) + fib(n-2);  //當 n > 50 你就會感覺很慢 !!!
} // fib
// 如上的 Recursive version 很好寫, 但因會叫用很多次, 會很慢 !
// === 以下改用 Iteration 方式則會很快很快!
// fib22(int) is a Loop version, i.e., fibLoop( )
long long fib22(int n) {  // Iteration version using for LOOP
   int i; long long f[999]={1, 1, 0}; // 第0個月與第一個月是 1
   for(i=2; i<=n; ++i) f[i] = f[i-1] + f[i-2];
   return f[n];
} // fib22
int getN( ) {
   int ntest[ ] = {19,35,36,37,38, 43,46,49,51, 90,91,92};
   static char buf[999];  static int i=0;
   if(i < (sizeof ntest / sizeof ntest[0]) ) {
      return ntest[i++];  // through the table ntest[ ]
   }
/// table ntest[ ] 用完後會用問的
   printf("\n n=? ");
   fgets(buf, sizeof(buf), stdin); 
   return atoi(buf); 
}
int main( ) {
   static char buf[888];
   long long ans;
   long long before, after, start, end, total;
   double elapsed;  // 用來算跑了幾秒?
   int n, w;  // 聽說 w 在籃球火 :-) 若 w 是 3388 則用 fib22( )
   printf("CLK_TCK=%f\n", (double)CLK_TCK );
   printf("CLOCKS_PER_SEC=%f\n", (double)CLOCKS_PER_SEC );
   printf("About to compute Fibonacci number..\n"
      " You can TRY n=19,35,36,37,38, 46,49,51, 90,91,92\n");
   printf("fib is a recursive version, fib22 uses LOOP.\n");
   printf("Enter 3388 for calling fib22, or I will call fib: ");
   fgets(buf, sizeof(buf), stdin);   // 讀入字串到 buf
   w = atoi(buf);   // call fib22( ) if w is 3388
 while(38==38) { 
   n = getN( );
   if(n==0) n = 19;  // 按 ENTER 算 19 :-)

   if(n<0) break;

   printf("  ..calling fib%s(%d)...", w==3388?"22":"", n);
   before = time(0);   start = clock();
   if(w==3388) ans =fib22(n);
   else ans = fib(n); //try n=19,30,36,37,38,45,46,49,90,91,92
   end = clock();   after = time(0);
    printf("...return from fib(%d)\n\n", n);
   total = end - start;  // in ticks
   elapsed = (double)total/CLOCKS_PER_SEC;  // in seconds
// DEV-C++ 底層是使用 GNU 的 MINGW32 gcc/g++
#ifdef __MINGW32__
  printf("Before call, time(0)=%I64d\n", before);
  printf(" After call, time(0)=%I64d\n", after);
#else
  printf("Before call, time(0)=%lld\n", before);
  printf(" After call, time(0)=%lld\n", after);
#endif
//////////
  printf("\nfib%s(%d)= ", w==3388?"22":"", n); //w是3388則是fib22
#ifdef __MINGW32__
  printf("%I64d\n", ans);
  printf(" Time used: %I64d ticks =", total);
#else
  printf("%lld\n",ans);
  printf(" Time used: %lld ticks =", total);
#endif
  printf("== %f seconds.\n", elapsed);   // elapsed 是實數喔!
 } // while
 /////////////
   printf("\nLib function difftime(t2, t1)=%f\n",
             difftime(end, start) );    // 其實它只是做減法 !
   printf(" What is the unit of difftime()?\n");  // tick 滴答
   printf(" Hit ENTER key .."); getchar( );  return 0;
} // main
/********** 以下是我的筆記型電腦跑出的結果.. (筆電通常比較慢)
D:\test> path C:\Dev-Cpp\bin;%path%
D:\test> gcc clockFib.c
D:\test> a.exe

...  注意: 直接按 ENTER 會用 Recursive version fib( ) 

fib(35)= 14930352

Time used: 28 ticks === 0.218750 seconds.


fib(36)= 24157817
 Time used: 46 ticks === 0.359375 seconds.


fib(37)= 39088169
 Time used: 74 ticks === 0.578125 seconds.


fib(38)= 63245986
 Time used: 120 ticks === 0.937500 seconds.


fib(39)= 102334155
 Time used: 193 ticks === 1.507812 seconds.


fib(40)= 165580141
 Time used: 315 ticks === 2.460938 seconds.


fib(41)= 267914296
 Time used: 510 ticks === 3.984375 seconds.


fib(42)= 433494437
 Time used: 824 ticks === 6.437500 seconds.


fib(43)= 701408733
 Time used: 1335 ticks === 10.429688 seconds.


fib22(44)= 1134903170
fib22(45)= 1836311903
fib22(46)= 2971215073
fib22(47)= 4807526976
fib22(48)= 7778742049
fib22(49)= 12586269025
fib22(50)= 20365011074
fib22(51)= 32951280099
fib22(52)= 53316291173
fib22(53)= 86267571272
fib22(54)= 139583862445
fib22(55)= 225851433717
fib22(56)= 365435296162
fib22(57)= 591286729879
fib22(58)= 956722026041

fib22(90)= 4660046610375530309
fib22(91)= 7540113804746346429
fib22(92)= -6246583658587674878   /// overflow long long 

預估算Fib(n)大約: (看你電腦快慢)
   44:  17 秒
   45:  28 秒
   46:  45 秒
   47:  73 秒
   48:  2分
   49:  3分
   50:  5分
   51:  8分
   52: 13分鐘
   53: 21分鐘
   54: 34分鐘
   55: 55分鐘
   56: 89分鐘

****************/