My Weblog

Blog about programming and math

SPOJ How many Fibs

TFIB is tutorial problem with relaxed time limit. Accepted Haskell code.

import Data.List

fib=1:2:zipWith (+) fib (tail fib)

main = do 
	   --line <-getLine
	   --let lst=words line
	       --a=read (lst!!0)::Integer
	       --b=read (lst!!1)::Integer
	   (a',b')<-fmap (span (/=' ')) getLine --using  functors
	   let a=read a'::Integer
	       b=read b'::Integer
	   case (and  [a==0,b==0] ) of 
			True -> return ()
			False-> do 
				  print $ length $ dropWhile (<a) $ takeWhile (<=b) fib

Another way to calculate Fibonacci numbers is matrix multiplication. See matrix form on Wiki. Haskell code

import Data.List
import Data.Bits
fibO n= recfibO ( [[1,1],[1,0]] ) n where
        recfibO m 1=m
        recfibO m 2=mult m m
        recfibO m n =
           p=recfibO (mult m m) (shiftR n 1 )
           q=if (.&.) n (fromIntegral 1) == 0 then p else mult p m
         in q

mult m t=[[sum $ zipWith (*) x y | y<- transpose t] | x<-m]

February 2, 2011 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: