フィボナッチ数の算法のベンチマーク

まずは、結果を下図に示します。

なおベンチマークに使用したコードは上記の説明コードとは違い、チューニング済みです。

逐次平方変換のコードは、dev68 さんの groovy 実装 をそのまま scala に移植しました。また、このエントリをきっかけとして、このエントリが生まれました。ありがとうございます。

Binet 公式のコードは、計算しなくて良い部分(wikipedia中の(-Φ)^(-n))を省いて高速化しています。この部分は、線形代数の言葉で言えば、「絶対値が1未満のほうの固有値」に一致します。ですから、線形代数的な観点からは、「絶対値が1未満のほうの固有値だから、冪乗を繰り返すとなくなっていくんだな」と、直感的に理解することも可能です。