みんなが大好きなフィボナッチ

Perl

フィボナッチ数列というのは，大抵のプログラムの本，それも再帰を扱っているものなら，まず出ているといってもよいほどの，人気者です．高校の数学の本にもまずでています．出ていなかった，きっと著者がフィボナッチが嫌いか，ウサギが嫌いなのに違いありません．

フィボナッチ数列というのは
$a_{n+2}=a_{n+1}+a_{n}\quad(n=1,2,\ldots), \quad a_1=1, a_2=1$
という漸化式で表される数列のことで，$a_1=1$，$a_2=1$，$a_3=a_1+a_2=2$，$a_4=a_2+a_3=3$，・・・のようになります．一般項を求めるのは本筋ではないので割愛します．これをPerlで素直に再帰で書くとこんな感じですね．

sub fib1{
    my $n = shift;
    return 0 if $n==0;
    return 1 if $n==1;
    return fib1($n-1)+fib1($n-2);
}

プログラムの場合，0から始めるのが多いようなので，0番目から始めることにしています．

ところがこれ，滅茶苦茶に遅くて，ちょっとでも大きい引数を与えるといらいらします．試みになんちゃってベンチマークをしてみます．

sub test{
    my ($n, $N, $callback) = @_;
    my $process_time;
    for my $i (1..$N){
	my $sttime=time;
	$callback->($n);
	my $endtime=time;
        $process_time += $endtime-$sttime;
    }
    return $process_time/$N;
}

print test(10, 1000, \&fib1),"\n";# 第10項を1000回計算して平均を出す
print test(20, 1000, \&fib1),"\n";# 第20項を1000回計算して平均を出す

1000回計算させて，平均を出してみると，私の機械だと

0.000156760215759277
0.0192136526107788

実は，30項目を計算させると，一回計算させるだけで2秒を突破します．1000回の平均なんて待ってられません．そこで第5項の計算を書き下してみると

fib(5) -- fib(4) + fib(3) -- fib(2) + 1
             |                 |
          fib(3) + fib(2)    1 + 1
             |       |
             |     1 + 1 
          fib(2) + 1 
             |
           1 + 1

どんどん枝分かれしていって，すごく早く計算が増えていきます．けど，よくみると同じ計算ばっかりしていることが分かるので，これを排除しようというのがHOPのテクニックです．

と，ここまで書いたんですが・・・haskellでフィボナッチ そしてPerlで書いてみたというページを発見。。。もう一年くらい前に同じことをしてる人がいた．ネタがなくなってしまったような気がしますが，予定通り先に進めようかと思います．