Evaluating Fibonacci-sequence-based recurrence relation (SPOJ Flibonakki)

Question

I have a function fib2 which returning two values as Tuple but I want to print the product of tuples returned by function fib2. I am new to Haskell so please explain it to me in a simple way.

This problem is from SPOJ which I have already solved using C and again I am trying it in Haskell:

For each \$n\$, find \$G(n) \mod 1000000007\$, where $$\begin{align*} G(0) &= 0 \\ G(n) &= G(n-1) + f(4n - 1), \qquad n > 0 \\ f(i) &= \mathrm{the\ i^{th}\ Fibobacci\ number} \end{align*}$$

The first line of input specifies the number of test cases.

Now my code is working fine but I'm getting TLE in this problem. Can someone show me how to optimize Fibonacci in Haskell?

import Data.List
import Data.Maybe
import Control.Monad
import qualified Data.ByteString.Char8 as C


fib2 0 = (1, 1)
fib2 1 = (1, 2)
fib2 n
 | even n    = ((a*a + b*b)`mod` 1000000007, (c*c - a*a)`mod` 1000000007)
 | otherwise = ((c*c - a*a)`mod` 1000000007, (b*b + c*c)`mod` 1000000007)
 where (a,b) = fib2 (n `div` 2 - 1)
       c     = a + b

solve n = (a*b)`mod`1000000007
    where (a,b) = fib2((2*n-1)`mod`2000000016)

main = C.getContents >>= putStrLn . unlines . map (show.solve.fromIntegral . fst . fromJust . C.readInteger) . tail . C.words

Answer 1

First of all, make sure to add type signatures and use the appropriate number type. All your numbers are fine with Int, since they're bounded by

2 * (1000000006 * 1000000006)

Therefore, you can get rid of Integer throughout your program and simply use Int:

fib2 :: Int -> (Int, Int)
fib2 0 = (1, 1)
fib2 1 = (1, 2)
fib2 n
 | even n    = ((a*a + b*b)`rem` 1000000007, (c*c - a*a)`rem` 1000000007)
 | otherwise = ((c*c - a*a)`rem` 1000000007, (b*b + c*c)`rem` 1000000007)
 where (a,b) = fib2 (n `quot` 2 - 1)
       c     = a + b

Next, you want to use rem and quot, since they're usually faster and provide the same result as mod and div on positive numbers.

We also add a type signature to solve:

solve :: Int -> Int
solve n = (a*b)`rem`1000000007
    where (a,b) = fib2((2*n-1)`rem`2000000016)

Last but not least, we now simplify your main:

main :: IO ()
main = C.getContents >>= putStrLn . unlines . map (show.solve. fst . fromJust . C.readInt) . tail . C.words

However, I don't think that the IO part is the bottle-neck, so your usual String methods should be fine for this challenge, e.g.

main = getContents >>= putStrLn . unlines . map (show . solve . read) . tail . words

Indeed, this version of your program gets accepted of SPOJ. But so did your one. I guess that they updated the GHC version* and used the appropriate optimization flags. But you can make sure that they use optimization via

{-# OPTIONS_GHC -O2 #-}

_{* I just rememered that there was a defect with even in GHC 7.10. If they used GHC 7.10 (which is unlikely), then you were affected by that defect.}