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" <[EMAIL PROTECTED]> wrote: > 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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
