ふぃぼる．

最も簡単に fib を高速化する方法 - ドレッシングのようなにむっちゃ早いfibが載ってた．

C的に書くと

#include <stdio.h>
#include <stdlib.h>


typedef struct double_ {
	int x0;
	int x1;
} Double;

int fib(int n);
Double *fib_f(int n);

int main(void)
{
	int i;

	for(i=1;i<40;i++){
		printf("%2d : %10d\n", i, fib(i));
	}
}

int fib(int n)
{
	Double *doub = fib_f(n);
	int ans = doub->x0;
	free(doub);

	return ans;
}

Double *fib_f(int n)
{
	Double *doub;
	if(n==1){
		doub = malloc(sizeof(Double));
		doub->x0 = 1;
		doub->x1 = 0;
	}else{
		doub = fib_f(n-1);
		int x0 = doub->x0;
		int x1 = doub->x1;
		doub->x0 = x0 + x1;
		doub->x1 = x0;
	}

	return doub;
}

となる．長いし汚い．ごめんね．