フィボナッチ数列の第k項をO(log n)で計算しようとしたけど難しかった話 - shogonir blog

目次 フィボナッチ数列 ビネの公式 計算誤差について 計算の工夫 最終的な計算時間 サンプルコード 1. フィボナッチ数列 フィボナッチ数列は、イタリアの数学者レオナルド・フィボナッチの名前をとって名付けられた数列です。 数列の決まりは、「ある項は、1つ前の項と2つ前の項の和である」というシンプルなものです。 数式にすると下記のようになります。 $$ F(k) = \left\{ \begin{array}{} 0 & ( k = 0) \\ 1 & ( k = 1) \\ F(k - 1) + F(k - 2) & ( k \geq 2) \end{array} \right. $$ このシンプルなルールの数列なのに、自然界の至る所で見ることができる興味深い数列です。 フィボナッチ数 - Wikipedia この記事では自然数 k が与えられた時に、フィボナッチ数列の第 k 項目を計算す