hayaのHaskell日記

2006-08-22

[] Tea break: Haskellフィボナッチ数列 00:58

定番の話題。

愚直に実装

fib :: Integer -> Integer
fib n
  | n < 0     = 0
  | n == 1    = 1
  | n == 2    = 1
  | otherwise = fib (n-1) + fib (n-2)

これだと、n < 100 で既に爆発する。

何が問題か

フィボナッチ数列の定義より、n番目の数値を得るためには、n-1番目とn-2番目の数を足す。n-1番目の数値を得るためにはn-2番目とn-3番目の数値を足す・・・と繰り返していくと、最終的に 1 + 1 の繰り返しまで還元される。ちなみに、50番目のフィボナッチ数は12586269025であるから、fib 50 を実行すると、+が12586269024個くらい並んだ式をHaskellは一旦生成し、それを計算していくのである。爆発している。

爆発シミュレーション

fib 6 = 8 を展開してみる。簡単のために、一部遅延評価とは異なる順序で簡約する。

fib 6
=> fib 5 + fib 4
=> (fib 4 + fib 3) + (fib 3 + fib 2)
=> ((fib 3 + fib 2) + (fib 2 + fib 1)) + ((fib 2 + fib 1) + fib 2)
=> (((fib 2 + fib 1) + fib 2) + (fib 2 + fib 1)) + ((fib 2 + fib 1) + fib 2)

fib 1 と fib 2 は共に1に置き換えられるから、あとは足し算をどんどんと実行していくだけである。最後の行には7個の+演算子がある。fibの現在の定義では、fib n を計算するときに、(fib n) - 1個の+演算子が並ぶことになる。

爆発する理由: フィボナッチ数列は指数関数的に増加する

フィボナッチ数列F_nの一般式は

F_n = \frac{1}{\sqrt{5}}\left{ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right}

であるから、フィボナッチ数はnに関して指数関数的に増加する。

つまり、計算量が指数関数的に増加するため、すぐに爆発してしまう。O\left(\left(\frac{1+\sqrt{5}}{2}\right)^n\right)アルゴリズムなのである。

より速いアルゴリズムを求めて

素直にググる

そして発見。http://kerolin.jspeed.jp/Computer/Linux/fib060810.html

2つ覚えれば、全てが解決する

普通人間がフィボナッチ数を計算するときはどうするだろうか。

1,1
=> 1,1, 1+1
=> 1,1,2, 1+2
=> 1,1,2,3, 2+3
=> 1,1,2,3,5, 3+5

のように計算していくが、注目しているのは常に計算しているフィボナッチ数の2つ前までである。2つより前の数は、忘れてしまってもフィボナッチ数は計算することができる。

前述の愚直な方法は、計算しているフィボナッチ数の前の2つの数字を覚えていなかった。何も覚えていなかったから、1 + 1になるまで遡って計算していたので、とんでもないことになっていたのである。

計算しては覚える、計算しては覚える、を繰り返していけば、n番目のフィボナッチ数を計算するときの計算量はO(n)になるのである。

じゃあ、実装を見てみるよ

http://kerolin.jspeed.jp/Computer/Linux/fib060810.html

に話を戻そう。

fibStep :: (Int, Int) -> (Int, Int)
fibStep (u, v) = (v, u+v)

fibPair :: Int -> (Int, Int)
fibPair n
  | n == 0    = (0, 1)
  | otherwise = fibStep (fibPair (n-1))

fastFib :: Int -> Int
fastFib = fst . fibPair

ついでに、とてもすばらしい書き下しがあるので引用させていただく。

fastFib 5
=> fst (fibPair 5)
=> fst (fibStep (fibPair 4))
=> fst (fibStep fibStep (fibPair 3))
=> fst (fibStep fibStep fibStep (fibPair 2))
=> fst (fibStep fibStep fibStep fibStep (fibPair 1))
=> fst (fibStep fibStep fibStep fibStep fibStep (fibPair 0))
=> fst (fibStep fibStep fibStep fibStep fibStep (0, 1))
=> fst (fibStep fibStep fibStep fibStep (1, 1))
=> fst (fibStep fibStep fibStep (1, 2))
=> fst (fibStep fibStep (2, 3))
=> fst (fibStep (3, 5))
=> fst (5, 7)
=> 5

2つの値を、タプルで覚える

フィボナッチ数列の注目している(覚えている)2つの数を、()で囲んで見る。順番に計算して、6番目のフィボナッチ数を求めてみよう。

(1,1),2,3,5,8,13,21,34,55, ....

この2つから、1+1でもう1つ先のフィボナッチ数2がわかる。その時点で、小さいほうのフィボナッチ数1はもう計算には不要になる。結果、注目しているフィボナッチ数は次のようになる。

1,(1,2),3,5,8,13,21,34,55, ....

同様に、1つ先のフィボナッチ数を計算して、不要になったフィボナッチ数を忘れると

1,1,(2,3),5,8,13,21,34,55, ....

繰り返し...

1,1,2,(3,5),8,13,21,34,55, ....

繰り返し...

1,1,2,3,(5,8),13,21,34,55, ....

やった、6番目のフィボナッチ数の値が得られた。

さて、ここで括弧で囲んだ部分を、タプルとみなしてみよう。すると、タプルの値の変化は

(1,1) => (1,2) => (2,3) => (3,5) => (5,8)

一回の => のタプルの値の変化を、Haskellで表現できるとうれしい。それに対応する関数が、fibStepである。

fibStep :: (Int, Int) -> (Int, Int)
fibStep (u, v) = (v, u+v)

fibStep (1,1) #=> (1,2)
fibStep (1,2) #=> (2,3)
fibStep (2,3) #=> (3,5)

(3,5) 
<= fibStep (2,3)
<= fibStep fibStep (1,2)
<= fibStep fibStep fibStep (1,1)
<= fibStep fibStep fibStep fibStep (0,1)

つまり、n番目のフィボナッチ数を得るには、(0,1)にn回fibStepを適用して、その結果得られたタプルの最初の値を取り出してやればいい。

この方法が愚直な方法と違って優れていることは、計算量がO(n)ですんでしまうことである。指数関数的に増加する計算時間を、多項式時間にできた(しかも1次の)ことにより、爆発的に計算が速く終了する。

ReynaldoReynaldo2007/05/11 17:13http://cb7a416616f2eb5dba240cf5837ca9fd-t.eslyki.info <a href="http://cb7a416616f2eb5dba240cf5837ca9fd-h.eslyki.info">cb7a416616f2eb5dba240cf5837ca9fd</a> [url]http://cb7a416616f2eb5dba240cf5837ca9fd-b1.eslyki.info[/url] [url=http://cb7a416616f2eb5dba240cf5837ca9fd-b2.eslyki.info]cb7a416616f2eb5dba240cf5837ca9fd[/url] [u]http://cb7a416616f2eb5dba240cf5837ca9fd-b3.eslyki.info[/u] 1918e506ec14eb4ca3235afa2674a1a4

トラックバック - http://haskell.g.hatena.ne.jp/harg/20060822