フィボナッチ数列

結城浩さんのミルカさんとフィボナッチ数列を読んでみた。すげー、フィボナッチ数列って一般項にできるんだなぁと思って3バージョンほど作って比較。
再帰を使ったバージョンは40項にもなるとかなり遅いんだけど、一般項はsqrt()関数を使ってもオーバーフローするまで*1丸め誤差の影響は出ないなぁ。
以下にソース公開。

fibonacci.c

#include <stdio.h>
#include "fibonacci.h"

int fibonacci3(int n);

int main(void){
	
	int n;
	
	while(1){
		printf("input n = ");
		scanf("%d",&n);
		if(n<0)break;
		printf("fibonacci(%d)          = %d\n",n,fibonacci(n));
		printf("fast_fibonacci(%d)     = %d\n",n,fast_fibonacci(n));
		printf("general_fibonacci3(%d) = %d\n",n,general_fibonacci(n));
		
	}
	puts("exit.");
	return 0;
}

fibonacci.h

/* 
 * フィボナッチ数列の第ｎ項を返す関数
 * n < 0 にはFIB_FAILURE を返す。
 * by Yuta 2005/10/23/
 */
 
#include <math.h>

#define FIB_FAILURE -1

/* 再帰版 */
int fibonacci(int n){
	if(n<0)return FIB_FAILURE;
	if(n==0)return 0;
	if(n==1)return 1;
	return fibonacci(n-1) + fibonacci(n-2);
}

/* ループ版 */
int fast_fibonacci(int n){
	int i;
	int a = 0;
	int b = 1;
	if(n<0)return FIB_FAILURE;
	if(n==0)return 0;
	if(n==1)return 1;
	
	for(i=0;i<n;i++){
		b += a;
		a = b - a; 
	}
	return a;
}

/* 一般項版 */
int general_fibonacci(int n){
	double ret = ((pow(1.0 + sqrt(5), n) - pow(1.0 - sqrt(5), n)) / (pow(2,n) * sqrt(5)));
	if(n<0)return FIB_FAILURE;	
	return (int)ret;
}

*1:n=46