高速フィボナッチ

Haskellで書きました。

matrix2 (x1,y1,z1,w1) (x2,y2,z2,w2) = (x2*x1+y1*z2 , x1*y2+y1*w2,x2*z1+w1*z2,y2*z1 + w1*w2)
repeat' n f x y
       | n < 1 = f x y 
       | n == 1 = f x y
       | n > 1 = repeat' (n-1) f (f x y) y
third (x,y,z,w) = z
matrxpow m n
      | n == 0 = (1,0,0,1)
      | n `mod` 2 == 0 = matrxpow (matrix2 m m) (n `div` 2)
      | otherwise = matrix2 m (matrxpow (matrix2 m m) (n `div` 2))
fib x = third ( matrxpow (1,1,1,0) (x))

線形な漸化式は行列で表示することができます。

\[ \left(
\begin{array}{cc}
a_{n+2} \\
a_{n+1}
\end{array}
\right)
=
\left(
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right)
\left(
\begin{array}{cc}
a_{n+1} \\
a_{n}
\end{array}
\right)
\]
これを繰り返し用いると、

\[ \left(
\begin{array}{cc}
a_{n+2} \\
a_{n+1}
\end{array}
\right)
=
\left(
\begin{array}{cc}
1 & 1 \\
1 & 0
\end{array}
\right)^{n+1}
\left(
\begin{array}{cc}
a_{1} \\
a_{0}
\end{array}
\right)
\]
\[(a_0 = 0 , a_1 = 1)\]
行列のべきと初期条件の積の形に変形できます。
このプログラムではこの行列のべきを計算し、2×2行列の左下の要素を取ってくることでフィボナッチ数列を計算しています。
このままではO(n)の多項式オーダーですが、行列のべきを求める関数 matrxpow m n (Int*Int*Int*Int -> Int -> Int*Int*Int*Int)に高速化処理をしました。
基底 : \[A^0 = I\]
行列の0乗は単位行列
帰納 : \[A^{2k+1} = A(AA)^k , k \in \mathbb{Z} , k≧0\]
\[A^{2k} = (AA)^k , k \in \mathbb{Z} , k≧0\]
べきの偶奇によって場合分けします。
結合律を満たす演算全般に有効です。