Here's some code I wrote a while back for computing the nth Fibonacci number. It has O(log n) time complexity rather than O(n). It isn't the most elegant example, but it should be one of the fastest approaches.

import Data.Bits (shiftR, xor, (.|.), (.&.)) import Data.Word (Word32)

fibo :: Word32 -> Integer fibo n = loop (highestBitMask n) 1 0 where loop :: Word32 -> Integer -> Integer -> Integer loop i a b | i == 0 = b | n .&. i /= 0 = (loop (shiftR i 1) $! a*(2*b + a)) $! a*a + b*b | otherwise = (loop (shiftR i 1) $! a*a + b*b) $! b*(2*a - b)

highestBitMask :: Word32 -> Word32 highestBitMask x = case (x .|. shiftR x 1) of x -> case (x .|. shiftR x 2) of x -> case (x .|. shiftR x 4) of x -> case (x .|. shiftR x 8) of x -> case (x .|. shiftR x 16) of x -> (x `xor` (shiftR x 1))

Cheers, Spencer Janssen On 6/15/06, Vladimir Portnykh 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Thu, 15 Jun 2006, Vladimir Portnykh 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 :).

The garbage collector will free storage for values that are no longer needed. So if the garbage collector is hard working there will be no more than 2 previous values stored per computation of a new value.

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.

If you want to do it that way, better use pairs of numbers instead of lists. Lists can have any number of elements, pairs have exactly two members. So the latter is more type safe.

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" 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe