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

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 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)mod1000000007
where (a,b) = fib2((2*n-1)mod2000000016)

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

• Basically, your code looks good. I get a ~25% speedup by making it a little stricter, !c = a + b in the where clause of fib2 (requires {-# LANGUAGE BangPatterns #-} at the top), and a small improvement from using quot and rem instead of div and mod. I'm not sure of the compile options SPOJ passes, so adding {-# OPTIONS_GHC -O2 #-} after the language pragma might be required. Commented Jan 9, 2015 at 21:10
• @DanielFischer Thanks for your answer. Yes I am getting compile error after changing c = a+b to !c = a + b getting Illegal bang-pattern (use -XBangPatterns). I will try to rectify this. Commented Jan 10, 2015 at 8:55
• EDIT1:: Yes using quot and rem I got 30% speed up. But Still TLE. Commented Jan 10, 2015 at 9:06
• You must put the language pragma at the top of the source file to use bang patterns. And have you also the optimisation pragma in the file? If SPOJ doesn't pass -O2 as a compilation flag, you absolutely need it. Commented Jan 10, 2015 at 10:12
• @DanielFischer that is an answer, please post it as such to allow voting on it Commented Dec 6, 2015 at 20:20

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)rem1000000007
where (a,b) = fib2((2*n-1)rem2000000016)


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.