フィボナッチ数を計算する多分最速の方法 - Qiita

はじめに 巷では、フィボナッチ数の計算がお手軽なベンチマークとして扱われているようです。フィボナッチ数の計算方法を調べると、とても遅いアルゴリズムが多数ヒットしてしまいます。 このままでは、フィボナッチ数を高速に計算したい人が途方にくれたり、この程度の計算量だと勘違いするかも知れません。なので、フィボナッチ数を高速に計算するアルゴリズムを紹介することにしました。 ビネの公式 フィボナッチ数とは、フィボナッチ数列のn項目の数$F_n$を指し、一般項は以下の式で表すことができます。 $$F_n = \frac{\phi^n - \bar{\phi}^n}{\sqrt{5}} \tag{1} $$$$ \phi = \frac{1 + \sqrt{5}}{2}, \bar{\phi} = \frac{1 - \sqrt{5}}{2} \tag{2}$$ 上記の式はビネの公式と呼ばれています。 気