フィボナッチ数列のプログラム

okamoto7さんの2007-11-30の手法に興味をもったので、実
際にプログラムを書いてみた。

ついでに再帰の方法と比べられるようにしてみた。

再帰の方は404 Blog Not Found:アルゴリズム百選 - フィボナッチ数列にO()を学ぶを参考にさせてもらいました。

#include 
#include 
using namespace std;

long long function(long long n_1, long long n_2, int c)
{
  if( c <= 2 ){
	return n_1;
  }
  return function(n_1 + n_2, n_1, c-1);
}

int main(int argc, char* argv[])
{
  struct timeval end;
  struct timeval start;
  int n = 0;

  if( argc > 1 ){
	if( 0 == sscanf( argv[1], "%d", &n ) ){
	  return 1;
	}
  }else{
	return 1;
  }

  cout << "recursive" << endl;
  gettimeofday(&start, NULL);
  for( int i =1; i < n; i++ ){
	cout << function(1, 1, i) << endl;
  }
  gettimeofday(&end, NULL);
  cout << "microseconds :" << end.tv_usec - start.tv_usec << endl;


  cout << "linear algebra" << endl;
  long long v_ahead[2] = {1, 1};
  long long v[2];
  long long m[2][2] = { {1, 1}, {1, 0} };

  gettimeofday(&start, NULL);
  cout << v_ahead[0] << endl;
  cout << v_ahead[1] << endl;
  for( int i = 3; i < n; i++){
	v[0] = m[0][0] * v_ahead[0] + m[0][1] * v_ahead[1];
	v[1] = m[1][0] * v_ahead[0] + m[1][1] * v_ahead[1];
	cout << v[0] << endl;

	v_ahead[0] = v[0];
	v_ahead[1] = v[1];
  }
  gettimeofday(&end, NULL);
  cout << "microseconds :" << end.tv_usec - start.tv_usec << endl;
  return 0;
}

実際にどれぐらいの差があるのか…

実際に測定しました。

その前に環境、ちなみにdmesgコマンドでCPUは

CPU1: Intel(R) Pentium(R) 4 CPU 3.00GHz

と出ています。
コンパイラはgcc（g++といったほうがいいのかな）

まず最適化無しで測定の結果

項数	再帰での計算時間(マイクロセカンド)	行列での計算時間(マイクロセカンド)
80	88	4
81	88	4
82	89	4
83	89	4
84	91	4
85	93	4
86	94	4
87	98	4
88	100	4
89	103	4
90	107	4
91	109	4
92	112	4

凄い差なんですね…

次に最適化あり（-O2オプション）で実行するとほとんど差がなくなりました…どうして？

再帰関数を使っている時の最適化って…ちょっと調べてみようかな。