How about the closed form ;)
-- fib x returns the x'th number in the fib sequence
fib :: Integer -> Integer
fib x = let phi = ( 1 + sqrt 5 ) / 2
in truncate( ( 1 / sqrt 5 ) * ( phi ^ x - phi' ^ x ) )
Seems pretty quick to me, even with sqrt and arbitrarily large numbers.
On 6/15/06 9:33 AM, "Vladimir Portnykh"
Fibonacci numbers implementations in Haskell one of the classical examples. An example I found is the following:
fibs :: [Int] fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)]
To get the k-th number you do the following: Result = fibs !! k
It is elegant but creates a list of all Fibonacci numbers less than k-th, and the code is not very readable :).
I wrote my own Fibonacci numbers generator:
fib :: Int -> [Int] fib 0 = [0,0] fib 1 = [1,0] fib n = [sum prevFib, head prevFib] where a = fib (n - 1)
To get the k-th number you do the following:
result = head (fib k)
It does not generate full list of Fibonacci numbers, but keeps only 2 previous numbers, and has only one recursive call. Because the list always has only 2 elements using the functions head and sum is a bit overkill.
Can we do better?
_________________________________________________________________ Are you using the latest version of MSN Messenger? Download MSN Messenger 7.5 today! http://join.msn.com/messenger/overview
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe