Fibonacci数の計算時間は入力が大きくなるとどうなるのだろう
「今ふつうに使える計算機でFibonacci数を計算するのにかかる時間は、70程度までならほぼ一定」というのはまあいいとして（よっぽどナイーブな実装でなければ一瞬だし）
「迷ったらbenchmark」という教えがあったから、Mathematicaで試してみた
Mathematicaは約5.2e-646456888から1.9e646456887までの数ならいろいろ難しいことを考えずに使えて便利なんだけど(Windows, 32bit版)、中がどうなっているかわからなくて気持ち悪い。マニュアルにはこれだけ
Fibonacci[n]はn の2進数列に基づく反復法を使用する．
同じ計算を何度もやらせて総時間を回数で割る、というのは怪しそう。Mathematicaの動作がまず不明だし、どこのキャッシュにどういうデータが入るのかなんて、考えてもよくわからない
賢い処理系はf(100)のあとにf(101)を計算するとき前の結果を使ったり、「なんだよ、同じ事の繰り返しじゃねえか、じゃあ、さっきの答えでいいよな」ってなったりするかなあ（もっと賢い処理系は「ああ、時間を計りたいのね、じゃあ素直にやってあげるよ」なんてことに）
というわけで、1回のセッションで1つの値を1回だけ計算するということにした（それでも入力が大きくなれば計れるくらいに時間がかかる）
rm -f tmp.txt
for (( p=1 ; $p < 31 ; p=$(($p+1)) ))
do
echo "{2^$p,CForm[Timing[Fibonacci[2^$p];][[1,1]]]}" | math >> tmp.txt
done
grep Out tmp.txt | sed 's/Out\[1\]= {\|,\|}//g' > result.txt結果（Athlon X2 4400+, メモリ2Gbで2^30まで）
Fibonacci[2^31]はオーバーフロー。ディスクを使うようなコードを書けばかなり先まで続けられるだろうけれど、傾向はかなり変わるだろうね
小さいときだけ見て、一定だと誤解してしまうのもしかたないか
実機で試すのも楽じゃないな
No related posts.
