えびちゃんの日記

えびちゃん(競プロ)の日記です。

行列累乗なしで Fibonacci 数列を求める

(注意)たぶんネタ記事です.素直に行列累乗してください*1

唐突なんですが,以下の式を \(10^9+9\) を法として計算してみましょう.

(308495997 ** i - 691504013 ** i) * 723398404

Python にまかせます.

>>> [(308495997 ** i - 691504013 ** i) * 723398404 % (10**9+9) for i in range(20)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

えー,Fibonacci 数列が計算できていますね.

解説

まず,そもそも,Fibonacci 数列の一般項は次のように求められます. \[F_n = (\sqrt{5})^{-1} \cdot (\phi^n - (-\phi^{-1})^n).\] ただし \(\phi = 2^{-1}\cdot (1+\sqrt{5})\) です.

ここで,\(\mathbb{F}_p\) 上での \(\sqrt{5}\),すなわち \(x^2 \equiv 5 \pmod{p}\) となるような \(x\) があったとします.それを用いて(適宜,逆元などを求めつつ)上式を計算することで Fibonacci 数列を計算することができます.

実用性?

えー,残念ながら \(\mathbb{F}_p\) 上で常に \(\sqrt{5}\) が存在するとは限らないんですよね*2

実際,\(p = 10^9+7\) では存在せず,それが本記事の冒頭の式の mod が \(10^9+9\) だった理由です.かなしいね.

*1:きたまさ法とかでもいいです.

*2:存在する場合は,baby-step giant-step 法や,Tonelli–Shanks 法などで求めることができます.