フィボナッチ数の計算時間を考える

諸般の事情により、相変わらずフィボナッチ数と格闘中です。

何人かの方が既に書かれていますが、フィボナッチ数を高速に計算する方法があります。
細かいバリエーションはありますが、以下のような漸化式を利用します。
F_2n-1 = F_n-1² + F_n²
F_2n = 2F_n-1F_n + F_n²
これを使うと、再帰を繰り返すたびに n が半分になるので、log n ステップで実行できます。
そこで実際に以下のようなプログラムを書いて、計算時間を調べてみることにしました。

fib = fst . fib'
fib' 0 = (0,1)
fib' n
    | even n    = (f0, f1)
    | otherwise = (f1, f2)
    where (p,q) = fib' $ n`div`2
          f0 = f2 - f1
          f1 = p^2+q^2
          f2 = 2*p*q+q^2

-- すごい数になるので、下10桁だけ表示
-- 当初、length.show によって桁数を表示していたが、show のコストが大きく、実行時間の大半を占めていたため、show を利用しない方法に変更
*Main> signum $ fib $ 2^21
1
(0.56 secs, 3700200 bytes)
*Main> signum $ fib $ 2^22
1
(1.23 secs, 524968 bytes)
*Main> signum $ fib $ 2^23
1
(2.70 secs, 524864 bytes)
*Main> signum $ fib $ 2^24
1
(6.41 secs, 524864 bytes)

残念ながら計算時間については、そこまで速くなりませんでした。
n が 2 倍になると計算時間もほぼ 2 倍で、O(n) になっているように見えます。
つまり、各ステップでの計算時間がどんどん増えてしまっているということです。
実際、整数の積の計算は各桁（ビット）の積の足し合わせなので、桁数を k とおくと O(k²) です。
F_n と F_n-1 の桁数はほぼ等しく、F_2n や F_2n-1 の桁数はこれらのおよそ 2 倍になります。
つまりステップを進めるごとに桁数は 2 倍、ステップごとの計算時間は 2² = 4 倍に増えてしまいます。
そうすると全体の計算時間は、公比 4 の等比級数の第 log n 項までの和で、これは結局 O(n) となるわけです。
[追記]Haskell の乗算は FFT によってO(k * log k)で実行できるそうです（要確認）。そうすると同じ等比級数でも、公比はもっと小さくなります。[/追記]

これを改善するにはどうしたらよいでしょうか。
まず思いつくのは、全ての桁が必要でなければ、適当に切り取ってしまうことです。
例えば最後の 10 桁だけ必要であれば、以下のように書くとO(log n) で計算できます。
逆に最初の何桁か必要なら、浮動小数点演算でやってしまうとか。
あ、でも指数部が足りないや。

fibMod m n = fst $ fibMod' m n
fibMod' _ 0 = (0,1)
fibMod' m n
    | even n    = (f0, f1)
    | otherwise = (f1, f2)
    where (a,b) = fibMod' m $ n`div`2
          f0 = (f2 - f1)`mod`m
          f1 = (a^2+b^2)`mod`m
          f2 = (2*a*b+b^2)`mod`m

*Main> fibMod (10^10) (2^1000)
8059253307
(0.02 secs, 4643848 bytes)
*Main> fibMod (10^10) (2^2000)
1878773307
(0.05 secs, 6705276 bytes)
*Main> fibMod (10^10) (2^3000)
898293307
(0.06 secs, 8891576 bytes)
*Main> fibMod (10^10) (2^4000)
5117813307
(0.08 secs, 11171556 bytes)

整数の積の計算を O(k²) から O(k^1.59) に改善する方法もあります（『アルゴリズムデザイン』に載ってます）が、全体の計算時間が等比級数の和であることは変わりないので、残念ながら計算時間のオーダーは改善されません。
ということで、n 番目のフィボナッチ数を求めるには、やはり O(n) の時間がかかってしまうようです。
4*10⁶ 番目のフィボナッチ数は求められますが、4*10¹⁰⁶ 番目のフィボナッチ数への道は遠いですね。

アルゴリズムデザイン