Euler25.hs

module Main where
{-- http://d.hatena.ne.jp/rst76/20090513/1242221572 --}


-- fib = 1:1:(zipWith (+) fib (tail fib))
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


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




euler25 = n
   where
      n = head [(m,n) |m<-[1..],  let n = fib m ,n>((10^999))]

main = print $ euler25

参考にしました
http://d.hatena.ne.jp/rst76/20090513/1242221572

http://d.hatena.ne.jp/mokehehe/20090510/logfib