Jun 2011
1 / 9
Jun 2011
Jan 2015
mukesh_iiitm
Jun '11

Could some one please tell me why this code is getting time limit exceed. This sequence is sum of F_3 + F_7 + F_11 .... + F_(4n+3) = F_2n*F_(2n+1) . Is time limit too tight for Haskell or i am missing some thing.
Thank you 

import Data.List
import qualified Data.ByteString.Char8 as BS
--matmul ::(Integral a ) => [[a]] -> [[a]] -> a -> [[a]] 
--matmul a b m = ( map.map ) ( \x -> mod x m ) $ map ( \x -> map (   sum.zipWith (*) x  )  ( transpose  b ) ) a
matmul :: [Integer] -> [Integer] -> Integer -> [Integer]
matmul [a,b,c,d] [e,f,g,h] m = [u,v,w,x] where 
	u = mod ( a*e + b*g ) m
	v = mod ( a*f + b*h ) m
	w = mod ( c*e + d*g ) m
	x = mod ( c*f + d*h ) m 
powM ::[Integer] -> Integer -> Integer -> [Integer]
powM a n m | n == 1 = a 
	   | n == 2 = matmul a a m
	   | even n = powM ( matmul a a m ) ( div n 2 ) m 
	   | otherwise = matmul a ( powM ( matmul a a m ) ( div n 2 ) m ) m 
readInt :: BS.ByteString -> Integer
readInt x = case BS.readInteger x of
              Just ( i , _ ) -> i
	      Nothing -> error " upseperable ints "
solve::Integer -> BS.ByteString
solve n = BS.pack.show $ c*d where 
	 [c,_,d,_] = powM [1,1,1,0] (2*n) 1000000007
	--([_,a,_]:_) = powM [[1,2,1],[0,5,3],[0,3,2]] n 1000000007
	-- f_3+f_7+f_11+f_15 = f_2n*f_(2n+1)
main = BS.interact $ BS.unlines. map ( solve.readInt ) . tail . BS.lines

  • created

    Jun '11

  • last reply

    Jan '15
  • 8

    replies

  • 1.4k

    views

  • 5

    users

  • 1

    link

mukesh_iiitm
Jun '11

Thank you for reply hendrik. This same code accepted in 0.62 but the best Haskell solution time is 0.46 so i guess there is some room for improvement but i don't think it could be the reason for time limit exceed. I think time limit is tight for functional languages . 

import Data.List
import qualified Data.ByteString.Lazy.Char8 as BS
matmul :: [Integer] -> [Integer] -> Integer -> [Integer]
matmul [a,b,c,d] [e,f,g,h] m = [u,v,w,x] where 
   u = mod ( a*e + b*g ) m
   v = mod ( a*f + b*h ) m
   w = mod ( c*e + d*g ) m
   x = mod ( c*f + d*h ) m 
powM ::[Integer] -> Integer -> Integer -> [Integer]
powM a n m | n == 1 = a 
      | n == 2 = matmul a a m
      | even n = powM ( matmul a a m ) ( div n 2 ) m 
      | otherwise = matmul a ( powM ( matmul a a m ) ( div n 2 ) m ) m 
readInt :: BS.ByteString -> Integer
readInt x = case BS.readInteger x of
              Just ( i , _ ) -> i
              Nothing -> error " upseperable ints "
solve::Integer -> BS.ByteString
solve n = BS.pack.show $ c where 
    [c,_,_,_] = powM [1,1,1,0] n 1000000007
   --([_,a,_]:_) = powM [[1,2,1],[0,5,3],[0,3,2]] n 1000000007
   -- f_3+f_7+f_11+f_15 = f_2n*f_(2n+1)
main = BS.interact $ BS.unlines. map ( solve.readInt ) . tail . BS.lines
hendrik
Jun '11

I couldn't get my own HASK solution AC. blush My power function seems to be a bit slow.
Then I took your version and modified the matmul function as I think it should be. AC finally in 0.44.

mukesh_iiitm
Jun '11

I think this problem is not solvable in Haskell according to my Haskell experience. Modified fibonnaci code by hendrik also getting time limit exceed.

import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
matmul :: [Integer] -> [Integer] -> Integer -> [Integer]
matmul [a,b,c] [d,e,f] m = [x,y,z] where
        y = (a*e + b*f) `mod` m
        z = (b*e + c*f) `mod` m
        x = y + z
powM ::[Integer] -> Integer -> Integer -> [Integer]
powM a n m | n == 1 = a 
	   | n == 2 = matmul a a m
	   | even n = powM ( matmul a a m ) ( div n 2 ) m 
	   | otherwise = matmul a ( powM ( matmul a a m ) ( div n 2 ) m ) m 
readInt :: BS.ByteString -> Integer
readInt  = fst.fromJust.BS.readInteger 
solve::Integer -> BS.ByteString
solve n = BS.pack.show $ mod ( c*d ) 1000000007 where 
	 [c,d,_] = powM [1,1,0] ( 2*n ) 1000000007
	--([_,a,_]:_) = powM [[1,2,1],[0,5,3],[0,3,2]] n 1000000007
	-- f_3+f_7+f_11+f_15 = f_2n*f_(2n+1)
main = BS.interact $ BS.unlines. map ( solve.readInt ) . tail . BS.lines
gorlum0_sof
Jun '11

Try to create less thunks in powM and use strictness annotations. Something like this:
[bbone=haskell,228]
powM ::[Integer] -> Integer -> Integer -> [Integer]
powM a n m result
| n == 1 = matmul a result
| n == 2 = matmul (matmul a a m) result
| even n = powM b n' m result
| otherwise = powM b n' m result'
where !b = matmul a a m
!result' = matmul a result
!n' = n div 2
[/bbone]
Invariant thinking: a^n * result = const.

Did you profile? Also BS.pack is kind of slow.. parse with ByteStrings but give basic print a shot (with and without interact).

1 year later
fedelebron
Jun '13

(Reviving due to new info)

I AC'd on the first try with Haskell, 1.58s. My IO is as follows:

[bbone=haskell,585]
main = C.getContents >>= putStr . unlines . map (show . f . fromIntegral . fst . fromJust . C.readInteger) . tail . C.words
[/bbone]

Where C is Data.ByteString.Char8.

1 year later
luckymastermin
Jan '15

Hi All I am new to haskell I am trying this problem for a while but having issue with output format.

[bbone=haskell,776]import Data.List
import Data.Maybe
import Control.Monad

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

main :: IO ()
main = do
testcase <- readLn
replicateM_ testcase (getLine >>= print.fib2.read)[/bbone]

The main issue is I am unable to print the produce of tuples returned by fib2 Please help me how to get the product of the two tuples.

NOTE :: I am completely new to Haskell so Please explain me in simple way.

Thanks.

luckymastermin
Jan '15

Hi All,

I have updated My algorithm But getting TLE now even with Fast IO mention by fedelebron .
here is My updated code.
[bbone=HASKELL,777]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)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
[/bbone]