A linear algebra view of Fibonacci sequence

はじめに

逐次平方変換
Binet公式

について、線形代数的な視点から説明を与えて、ベンチマークしてみました。

なおどちらの方法についても、詳しい説明は世の中に出回っているはずですが、私にとってそれらの説明は天才のひらめきのような印象が拭えませんでした。そこで、あえて線形代数観点から説明を与えることで、「誰もが思いつきそうな、ありきたりの手法じゃないか」と感じて頂けたら嬉しいです。

なお、以下ではフィボナッチ数列の初項を F_0 = 0, F_1 = 1 としました。

逐次平方変換

フィボナッチ数列の漸化式を下記のように表現します：
$[\array{F_n \quad F_{n-1} \\ F_{n-1} \quad F_{n-2}}] = [\array{1 \quad 1 \\ 1 \quad 0}] [\array{F_{n-1} \quad F_{n-2} \\ F_{n-2} \quad F_{n-3}}]$

初項と係数行列が等しいことに注意すれば、下記のようになります。

$[\array{F_n \quad F_{n-1} \\ F_{n-1} \quad F_{n-2}}] = [\array{1 \quad 1 \\ 1 \quad 0}]^{n-1}$

ここで行列の結合性をもちいて、冪乗を下記の擬似コードのように O(log N) で計算すると、いわゆる逐次平方変換と等価な式が得られます。

// O(log N) な冪乗計算
def pow(b: Matrix, e: Int): Long =
  if (e == 0) IdentityMatrix 
  else (e % 2) match {
    case 0 => pow(b * b, e / 2)
    case 1 => b * pow(b, e - 1)
  }
}