SPOJ How many Fibs

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

import Data.List

fib::[Integer]
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
				  main 

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

import Data.List
import Data.Bits
--http://en.wikipedia.org/wiki/Fibonacci_number
fibO::Integer->[[Integer]]
fibO n= recfibO ( [[1,1],[1,0]] ) n where
        recfibO m 1=m
        recfibO m 2=mult m m
        recfibO m n =
         let    
           p=recfibO (mult m m) (shiftR n 1 )
           q=if (.&.) n (fromIntegral 1) == 0 then p else mult p m
         in q

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

About these ads