読者です 読者をやめる 読者になる 読者になる

タプリング

Haskell

F_{3n}F_{3n+1}とからS_{n}がもとまるわけである.F_{3n}がわかるので項の値の限界の設定も可能である.しかし,F_{3n}F_{3n+1}を独立に計算するのは樹状再帰になって効率が悪い.そこで,Fibonacci数列では定石のタプリングを考える.
E_{n} = (F_{3n}, F_{3n+1})
とする.,S_{n}E_{n}が求まれば求まるわけである.さて,
[tex:\begin{array}{rcl}E_{n+1} &=& (F_{3n+3}, F_{3n+4})\\ &=& (F_{3n+2}+F_{3n+1},F_{3n+3}+F_{3n+2})\\ &=& *1\\ &=& (F_{3n}+2F_{3n+1},(F_{3n}+2F_{3n+1})+(F_{3n}+F_{3n+1}))\\ &=& (F_{3n}+2F_{3n+1},2F_{3n}+3F_{3n+1})\end{array}]
だから,以下のようにするとO(n)E_{n}は求まる.すなわち,S_{n}O(n)で求まる.しかし,これでは最初のものと同じ計算オーダーなので本質的な改善にはならそう.

e :: Integer             -- upper bound
  -> (Integer,Integer)
e x = e' (x<) (0,1) (2,3)

e' :: (Integer -> Bool) 
   -> (Integer, Integer) 
   -> (Integer, Integer) 
   -> (Integer, Integer)
e' p ab@(a,b) cd@(c,d) 
 | p c       = ab
 | otherwise = e' p cd cd'
               where cd'@(c',d') = (a+2*b,2*c'-b)

s :: Integer             -- upper bound
  -> Integer
s x = (a+b-1) `div` 2
  where (a,b) = e x

*1:F_{3n}+F_{3n+1})+F_{3n+1},F_{3n+3}+(F_{3n}+F_{3n+1}