6
\$\begingroup\$

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
\$\endgroup\$
12
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Jan 9, 2015 at 21:10
  • \$\begingroup\$ @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. \$\endgroup\$
    – Lakshman
    Jan 10, 2015 at 8:55
  • \$\begingroup\$ EDIT1:: Yes using quot and rem I got 30% speed up. But Still TLE. \$\endgroup\$
    – Lakshman
    Jan 10, 2015 at 9:06
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 10, 2015 at 10:12
  • 2
    \$\begingroup\$ @DanielFischer that is an answer, please post it as such to allow voting on it \$\endgroup\$
    – Caridorc
    Dec 6, 2015 at 20:20

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.