Personal tools

The Fibonacci sequence

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(See also)
(A version using some identities)
 
(20 intermediate revisions by 11 users not shown)
Line 1: Line 1:
Implementing the [http://en.wikipedia.org/wiki/Fibonacci_number fibonacci sequence] is considered the "Hello, world!" of Haskell programming. This page collects Haskell implementations of the sequence.
+
Implementing the [http://en.wikipedia.org/wiki/Fibonacci_number Fibonacci sequence] is considered the "Hello, world!" of Haskell programming. This page collects Haskell implementations of the sequence.
   
== Naive solution ==
+
== Naive definition ==
   
  +
The standard definition can be expressed directly:
 
<haskell>
 
<haskell>
 
fib 0 = 0
 
fib 0 = 0
Line 8: Line 9:
 
fib n = fib (n-1) + fib (n-2)
 
fib n = fib (n-1) + fib (n-2)
 
</haskell>
 
</haskell>
  +
This implementation requires ''O(fib n)'' additions.
   
== Canonical zipWith implementation ==
+
== Linear operation implementations ==
  +
  +
=== With state ===
  +
Haskell translation of python algo
   
 
<haskell>
 
<haskell>
fib = 1 : 1 : zipWith (+) fib (tail fib)
+
{- def fib(n):
  +
a, b = 0, 1
  +
for _ in xrange(n):
  +
a, b = b, a + b
  +
return a -}
 
</haskell>
 
</haskell>
   
== With scanl ==
+
==== Tail recursive ====
   
  +
Using accumulator argument for state passing
 
<haskell>
 
<haskell>
fib = fix ((1:) . scanl (+) 1)
+
{-# LANGUAGE BangPatterns #-}
  +
fib n = go n (0,1)
  +
where
  +
go !n (!a, !b) | n==0 = a
  +
| otherwise = go (n-1) (b, a+b)
 
</haskell>
 
</haskell>
   
== With unfoldr ==
+
==== Monadic ====
  +
<haskell>
  +
import Control.Monad.State
  +
fib n = flip evalState (0,1) $ do
  +
forM [0..(n-1)] $ \_ -> do
  +
(a,b) <- get
  +
put (b,a+b)
  +
(a,b) <- get
  +
return a
  +
</haskell>
  +
  +
=== Using the infinite list of Fibonacci numbers ===
  +
  +
One can compute the first ''n'' Fibonacci numbers with ''O(n)'' additions.
  +
If <hask>fibs</hask> is the infinite list of Fibonacci numbers, one can define
  +
<haskell>
  +
fib n = fibs!!n
  +
</haskell>
  +
  +
==== Canonical zipWith implementation ====
  +
  +
<haskell>
  +
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
  +
</haskell>
  +
  +
==== With direct self-reference ====
  +
  +
<haskell>
  +
fibs = 0 : 1 : next fibs
  +
where
  +
next (a : t@(b:_)) = (a+b) : next t
  +
</haskell>
  +
  +
==== With scanl ====
  +
  +
<haskell>
  +
fibs = scanl (+) 0 (1:fibs)
  +
fibs = 0 : scanl (+) 1 fibs
  +
</haskell>
  +
The recursion can be replaced with <hask>fix</hask>:
  +
<haskell>
  +
fibs = fix (scanl (+) 0 . (1:))
  +
fibs = fix ((0:) . scanl (+) 1)
  +
</haskell>
  +
  +
The <code>fix</code> used here has to be implemented through sharing, <code>fix f = xs where xs = f xs</code>, not code replication, <code>fix f = f (fix f)</code>, to avoid quadratic behaviour.
  +
  +
==== With unfoldr ====
  +
  +
<haskell>
  +
fibs = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)
  +
</haskell>
  +
  +
==== With iterate ====
   
 
<haskell>
 
<haskell>
unfoldr (\(f1,f2) -> Just (f1,(f2,f1+f2))) (0,1)
+
fibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)
 
</haskell>
 
</haskell>
   
== A fairly fast version, using some identities ==
+
=== A version using some identities ===
   
 
<haskell>
 
<haskell>
Line 40: Line 43:
 
</haskell>
 
</haskell>
   
== Another fast fib ==
+
This seems to use <math>O(log^2 n)</math> calls to <code>fib</code>.
   
  +
== Logarithmic operation implementations ==
  +
  +
=== Using 2x2 matrices ===
  +
  +
The argument of <hask>iterate</hask> above is a [http://en.wikipedia.org/wiki/Linear_map linear transformation], so we can represent it as matrix and compute the ''n''th power of this matrix with ''O(log n)'' multiplications and additions.
  +
For example, using the [[Prelude_extensions#Matrices|simple matrix implementation]] in [[Prelude extensions]],
  +
<haskell>
  +
fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])
  +
</haskell>
  +
This technique works for any linear recurrence.
  +
  +
=== Another fast fib ===
  +
  +
(Assumes that the sequence starts with 1.)
 
<haskell>
 
<haskell>
 
fib = fst . fib2
 
fib = fst . fib2
Line 55: Line 72:
 
</haskell>
 
</haskell>
   
== Fastest Fib in the West ==
+
=== Fastest Fib in the West ===
   
 
This was contributed by [http://www.haskell.org/pipermail/haskell-cafe/2005-January/008839.html wli]
 
This was contributed by [http://www.haskell.org/pipermail/haskell-cafe/2005-January/008839.html wli]
  +
(It assumes that the sequence starts with 1.)
   
 
<haskell>
 
<haskell>
import System.Environment
 
 
import Data.List
 
import Data.List
   
fib n = snd . foldl fib' (1, 0) . map (toEnum . fromIntegral) $ unfoldl divs n
+
fib1 n = snd . foldl fib' (1, 0) . map (toEnum . fromIntegral) $ unfoldl divs n
 
where
 
where
 
unfoldl f x = case f x of
 
unfoldl f x = case f x of
Line 75: Line 92:
 
| p = (f*(f+2*g), f^2 + g^2)
 
| p = (f*(f+2*g), f^2 + g^2)
 
| otherwise = (f^2+g^2, g*(2*f-g))
 
| otherwise = (f^2+g^2, g*(2*f-g))
  +
</haskell>
   
main = getArgs >>= mapM_ (print . fib . read)
+
An even faster version, given later by wli on the [[IRC channel]].
  +
<haskell>
  +
import Data.List
  +
import Data.Bits
  +
  +
fib :: Int -> Integer
  +
fib n = snd . foldl' fib' (1, 0) . dropWhile not $
  +
[testBit n k | k <- let s = bitSize n in [s-1,s-2..0]]
  +
where
  +
fib' (f, g) p
  +
| p = (f*(f+2*g), ss)
  +
| otherwise = (ss, g*(2*f-g))
  +
where ss = f*f+g*g
 
</haskell>
 
</haskell>
  +
  +
== Constant-time implementations ==
  +
  +
The Fibonacci numbers can be computed in constant time using Binet's formula.
  +
However, that only works well within the range of floating-point numbers
  +
available on your platform. Implementing Binet's formula in such a way that it computes exact results for all integers generally doesn't result in a terribly efficient implementation when compared to the programs above which use a logarithmic number of operations (and work in linear time).
  +
  +
Beyond that, you can use [http://haskell.org/haskellwiki/Applications_and_libraries/Mathematics#Real_and_rational_numbers unlimited-precision floating-point numbers],
  +
but the result will probably not be any better than the [[#Log-time_implementations|log-time implementations]] above.
  +
  +
=== Using Binet's formula ===
  +
  +
<haskell>
  +
fib n = round $ phi ** fromIntegral n / sq5
  +
where
  +
sq5 = sqrt 5 :: Double
  +
phi = (1 + sq5) / 2
  +
</haskell>
  +
  +
== Generalization of Fibonacci numbers ==
  +
The numbers of the traditional Fibonacci sequence are formed by summing its two preceding numbers, with starting values 0 and 1. Variations of the sequence can be obtained by using different starting values and summing a different number of predecessors.
  +
  +
=== Fibonacci ''n''-Step Numbers ===
  +
The sequence of Fibonacci ''n''-step numbers are formed by summing ''n'' predecessors, using (''n''-1) zeros and a single 1 as starting values:
  +
<math>
  +
F^{(n)}_k :=
  +
\begin{cases}
  +
0 & \mbox{if } 0 \leq k < n-1 \\
  +
1 & \mbox{if } k = n-1 \\
  +
\sum\limits_{i=k-n}^{(k-1)} F^{(n)}_i & \mbox{otherwise} \\
  +
\end{cases}
  +
</math>
  +
  +
Note that the summation in the current definition has a time complexity of ''O(n)'', assuming we memoize previously computed numbers of the sequence. We can do better than. Observe that in the following Tribonacci sequence, we compute the number 81 by summing up 13, 24 and 44:
  +
  +
<math>
  +
F^{(3)} = 0,0,1,1,2,4,7,\underbrace{13,24,44},81,149, \ldots
  +
</math>
  +
  +
The number 149 is computed in a similar way, but can also be computed as follows:
  +
  +
<math>
  +
149 = 24 + 44 + 81 = (13 + 24 + 44) + 81 - 13 = 81 + 81 - 13 = 2\cdot 81 - 13
  +
</math>
  +
  +
And hence, an equivalent definition of the Fibonacci ''n''-step numbers sequence is:
  +
  +
<math>
  +
F^{(n)}_k :=
  +
\begin{cases}
  +
0 & \mbox{if } 0 \leq k < n-1 \\
  +
1 & \mbox{if } k = n-1 \\
  +
1 & \mbox{if } k = n \\
  +
F^{(n)}_k := 2F^{(n)}_{k-1}-F^{(n)}_{k-(n+1)} & \mbox{otherwise} \\
  +
\end{cases}
  +
</math>
  +
  +
''(Notice the extra case that is needed)''
  +
  +
Transforming this directly into Haskell gives us:
  +
<haskell>
  +
nfibs n = replicate (n-1) 0 ++ 1 : 1 :
  +
zipWith (\b a -> 2*b-a) (drop n (nfibs n)) (nfibs n)
  +
</haskell>
  +
This version, however, is slow since the computation of <hask>nfibs n</hask> is not shared. Naming the result using a let-binding and making the lambda pointfree results in:
  +
<haskell>
  +
nfibs n = let r = replicate (n-1) 0 ++ 1 : 1 : zipWith ((-).(2*)) (drop n r) r
  +
in r
  +
</haskell>
  +
   
 
== See also ==
 
== See also ==
   
  +
* [http://cgi.cse.unsw.edu.au/~dons/blog/2007/11/29 Naive parallel, multicore version]
  +
* [[Fibonacci primes in parallel]]
 
* [http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623 Discussion at haskell cafe]
 
* [http://comments.gmane.org/gmane.comp.lang.haskell.cafe/19623 Discussion at haskell cafe]
 
* [http://www.cubbi.org/serious/fibonacci/haskell.html Some other nice solutions]
 
* [http://www.cubbi.org/serious/fibonacci/haskell.html Some other nice solutions]
  +
* In [http://projecteuler.net/ Project Euler], some of the problems involve Fibonacci numbers. There are some solutions in Haskell ('''Spoiler Warning:''' Do not look at solutions to Project Euler problems until you have solved the problems on your own.):
  +
** [[Euler_problems/1_to_10#Problem_2|Problem 2]]
  +
** [[Euler_problems/21_to_30#Problem_25|Problem 25]]
  +
** [[Euler_problems/101_to_110#Problem_104|Problem 104]]
  +
** [[Euler_problems/131_to_140#Problem_137|Problem 137]]
   
 
[[Category:Code]]
 
[[Category:Code]]

Latest revision as of 17:46, 2 August 2012

Implementing the Fibonacci sequence is considered the "Hello, world!" of Haskell programming. This page collects Haskell implementations of the sequence.

Contents

[edit] 1 Naive definition

The standard definition can be expressed directly:

fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

This implementation requires O(fib n) additions.

[edit] 2 Linear operation implementations

[edit] 2.1 With state

Haskell translation of python algo

{- def fib(n):
      a, b = 0, 1
      for _ in xrange(n):
          a, b = b, a + b
      return a  -}

[edit] 2.1.1 Tail recursive

Using accumulator argument for state passing

{-# LANGUAGE BangPatterns #-}
fib n = go n (0,1)
  where
    go !n (!a, !b) | n==0      = a
                   | otherwise = go (n-1) (b, a+b)

[edit] 2.1.2 Monadic

import Control.Monad.State
fib n = flip evalState (0,1) $ do
  forM [0..(n-1)] $ \_ -> do
    (a,b) <- get
    put (b,a+b)
  (a,b) <- get
  return a

[edit] 2.2 Using the infinite list of Fibonacci numbers

One can compute the first n Fibonacci numbers with O(n) additions.

If
fibs
is the infinite list of Fibonacci numbers, one can define
fib n = fibs!!n

[edit] 2.2.1 Canonical zipWith implementation

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

[edit] 2.2.2 With direct self-reference

fibs = 0 : 1 : next fibs
  where
    next (a : t@(b:_)) = (a+b) : next t

[edit] 2.2.3 With scanl

fibs = scanl (+) 0 (1:fibs)
fibs = 0 : scanl (+) 1 fibs
The recursion can be replaced with
fix
:
fibs = fix (scanl (+) 0 . (1:))
fibs = fix ((0:) . scanl (+) 1)

The fix used here has to be implemented through sharing, fix f = xs where xs = f xs, not code replication, fix f = f (fix f), to avoid quadratic behaviour.

[edit] 2.2.4 With unfoldr

fibs = unfoldr (\(a,b) -> Just (a,(b,a+b))) (0,1)

[edit] 2.2.5 With iterate

fibs = map fst $ iterate (\(a,b) -> (b,a+b)) (0,1)

[edit] 2.3 A version using some identities

fib 0 = 0
fib 1 = 1
fib n | even n         = f1 * (f1 + 2 * f2)
      | n `mod` 4 == 1 = (2 * f1 + f2) * (2 * f1 - f2) + 2
      | otherwise      = (2 * f1 + f2) * (2 * f1 - f2) - 2
   where k = n `div` 2
         f1 = fib k
         f2 = fib (k-1)

This seems to use O(log2n) calls to fib.

[edit] 3 Logarithmic operation implementations

[edit] 3.1 Using 2x2 matrices

The argument of
iterate
above is a linear transformation, so we can represent it as matrix and compute the nth power of this matrix with O(log n) multiplications and additions.

For example, using the simple matrix implementation in Prelude extensions,

fib n = head (apply (Matrix [[0,1], [1,1]] ^ n) [0,1])

This technique works for any linear recurrence.

[edit] 3.2 Another fast fib

(Assumes that the sequence starts with 1.)

fib = fst . fib2
 
-- | Return (fib n, fib (n + 1))
fib2 0 = (1, 1)
fib2 1 = (1, 2)
fib2 n
 | even n    = (a*a + b*b, c*c - a*a)
 | otherwise = (c*c - a*a, b*b + c*c)
 where (a,b) = fib2 (n `div` 2 - 1)
       c     = a + b

[edit] 3.3 Fastest Fib in the West

This was contributed by wli (It assumes that the sequence starts with 1.)

import Data.List
 
fib1 n = snd . foldl fib' (1, 0) . map (toEnum . fromIntegral) $ unfoldl divs n
    where
        unfoldl f x = case f x of
                Nothing     -> []
                Just (u, v) -> unfoldl f v ++ [u]
 
        divs 0 = Nothing
        divs k = Just (uncurry (flip (,)) (k `divMod` 2))
 
        fib' (f, g) p
            | p         = (f*(f+2*g), f^2 + g^2)
            | otherwise = (f^2+g^2,   g*(2*f-g))

An even faster version, given later by wli on the IRC channel.

import Data.List
import Data.Bits
 
fib :: Int -> Integer
fib n = snd . foldl' fib' (1, 0) . dropWhile not $
            [testBit n k | k <- let s = bitSize n in [s-1,s-2..0]]
    where
        fib' (f, g) p
            | p         = (f*(f+2*g), ss)
            | otherwise = (ss, g*(2*f-g))
            where ss = f*f+g*g

[edit] 4 Constant-time implementations

The Fibonacci numbers can be computed in constant time using Binet's formula. However, that only works well within the range of floating-point numbers available on your platform. Implementing Binet's formula in such a way that it computes exact results for all integers generally doesn't result in a terribly efficient implementation when compared to the programs above which use a logarithmic number of operations (and work in linear time).

Beyond that, you can use unlimited-precision floating-point numbers, but the result will probably not be any better than the log-time implementations above.

[edit] 4.1 Using Binet's formula

fib n = round $ phi ** fromIntegral n / sq5
  where
    sq5 = sqrt 5 :: Double
    phi = (1 + sq5) / 2

[edit] 5 Generalization of Fibonacci numbers

The numbers of the traditional Fibonacci sequence are formed by summing its two preceding numbers, with starting values 0 and 1. Variations of the sequence can be obtained by using different starting values and summing a different number of predecessors.

[edit] 5.1 Fibonacci n-Step Numbers

The sequence of Fibonacci n-step numbers are formed by summing n predecessors, using (n-1) zeros and a single 1 as starting values: 
  F^{(n)}_k :=
  \begin{cases}
    0             & \mbox{if } 0 \leq k < n-1 \\
    1             & \mbox{if } k = n-1 \\
    \sum\limits_{i=k-n}^{(k-1)} F^{(n)}_i & \mbox{otherwise} \\
   \end{cases}

Note that the summation in the current definition has a time complexity of O(n), assuming we memoize previously computed numbers of the sequence. We can do better than. Observe that in the following Tribonacci sequence, we compute the number 81 by summing up 13, 24 and 44:


F^{(3)} = 0,0,1,1,2,4,7,\underbrace{13,24,44},81,149, \ldots

The number 149 is computed in a similar way, but can also be computed as follows:


149 = 24 + 44 + 81 = (13 + 24 + 44) + 81 - 13 = 81 + 81 - 13 = 2\cdot 81 - 13

And hence, an equivalent definition of the Fibonacci n-step numbers sequence is:


  F^{(n)}_k :=
  \begin{cases}
    0             & \mbox{if } 0 \leq k < n-1 \\
    1             & \mbox{if } k = n-1 \\
    1             & \mbox{if } k = n \\
    F^{(n)}_k := 2F^{(n)}_{k-1}-F^{(n)}_{k-(n+1)} & \mbox{otherwise} \\
   \end{cases}

(Notice the extra case that is needed)

Transforming this directly into Haskell gives us:

nfibs n = replicate (n-1) 0 ++ 1 : 1 :
          zipWith (\b a -> 2*b-a) (drop n (nfibs n)) (nfibs n)
This version, however, is slow since the computation of
nfibs n
is not shared. Naming the result using a let-binding and making the lambda pointfree results in:
nfibs n = let r = replicate (n-1) 0 ++ 1 : 1 : zipWith ((-).(2*)) (drop n r) r
          in r


[edit] 6 See also