高速フィボナッチ

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行列の左下の要素を取ってくることでフィボナッチ数列を計算しています。
行列のべきを求める関数 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\]
べき数の偶奇によって場合分けします。