Fibonacci数の反復アルゴリズムを考える

(1)$ F_{m + n} = F_{m}F_{n+1} + (F_{m+1} - F_{m})F_{n}

(2)$ F_{m+n+1} = F_{m+1}F_{n+1} + F_{m}F_{n}

(3)$ F_{2n} = 2F_{n+1}F_{n} - F_{n}^{2}

(4) $ F_{2n+1} = F_{n+1}^2 + F_{n}^2

$ \mathbb{F}_{n} \triangleq (F_{n+1}, F_{n})

$ \mathbb{F}_{m+n} = (F_{m+1}F_{n+1} + F_{m}F_{n},\;\;F_{m}F_{n+1} + (F_{m+1} - F_{m})F_{n})

$ \mathbb{F}_{2n} = (F_{n+1}^2 + F_{n}^2,\;\;2F_{n+1}F_{n} - F_{n}^2)

逐次平方と同じ考え方

$ \mathbb{ab} = \mathbb{F}_{i}，$ \mathbb{pq} = \mathbb{F}_{j = 2^k}，$ mの3つを反復状態変数とする．

初期値はそれぞれ，$ \mathbb{F}_{0}，$ \mathbb{F}_{1}，$ n

反復不変条件は，$ i+j \cdot m = n

状態の更新は以下のようにする．

$ mが偶数のとき

$ \mathbb{F}_{i}:(a, b) \leftarrow \mathbb{F}_{i}:(a, b)

$ \mathbb{F}_{j}:(p, q) \leftarrow \mathbb{F}_{2j}:(p^2 + q^2, 2pq - q^2)

$ mが奇数のとき

$ \mathbb{F}_{i}:(a, b) \leftarrow \mathbb{F}_{i+j}:(pa + qb, qa + (p-q)b)

$ \mathbb{F}_{j}:(p, q) \leftarrow \mathbb{F}_{j}:(p, q)

code:FibIter.hs

fibIter :: (Natural, Natural) -> (Natural, Natural) -> Natural -> Natural

fibIter (!a, b) (p, q) = \ case

0 -> b

n'@(n+1)

| even n' -> fibIter (a, b) (p*p + q*q, (p + p - q)*q) (n' div 2)

| otherwise -> fibIter (p*a + q*b, q*a + (p - q)*b) (p, q) n