タプリング - HaHaHa!

$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}