SICP : Ex1.19
これは、フィボナッチ数を行列を使って高速に計算するという問題。
フィボナッチ数とは、以下の漸化式で与えられる数列。
a_{0} = 0 a_{1} = 1 a_{n+2} = a_{n+1} + a_{n}
これを行列を用いて、以下のように表すことができる。ただし、p=0, q=1。
|a_{n+2}| = |(p+q) q| |a_{n+1}| |a_{n+1}| | q p| |a_{n} |
ここで、以下のようにTを置くと、
T = |(p+q) q| | q p|
a_{n}は、以下のように書き直すことができる。
|a_{n+1}| = (T^n) |1| |a_{n} | |0|
T^2が以下のようになることを用いて、高速な累乗計算と同じ手法でフィボナッチ数を計算することができる。
T^2 = |(p`+q`) q`| | q` p`| where p` = p^2 + q^2 q` = 2pq + q^2
回答
ということで、Concurrent Cleanを用いた解はこちら。
fib :: Int -> Int fib n = fib_itr 1 0 0 1 n fib_itr :: Int Int Int Int Int -> Int fib_itr _ b _ _ 0 = b fib_itr a b p q count | isEven count = fib_itr a b (p^2+q^2) ((2*p+q)*q) (count/2) | otherwise = fib_itr ((p+q)*a+q*b) (q*a+p*b) p q (count-1)