| Portability | portable |
|---|---|
| Stability | experimental |
| Maintainer | Sebastian Fischer |
Data.Numbers.Fibonacci
Description
Fast computation of Fibonacci numbers. Use version 0.1.* if you
prefer the Fibonacci sequence to start with one instead of
zero. Version 0.2.* adds correct handling of negative arguments
and changes the implementation to satisfy fib 0 = 0.
See http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form for a description of the employed method.
Documentation
fib :: (Integral int, Num num) => int -> numSource
Computes Fibonacci numbers. Yields the same results as
fib 0 = 0
fib 1 = 1
fib n | n > 1 = fib (n-2) + fib (n-1)
| n < 0 = (-1)^(1-n) * fib (-n)
but more efficiently.
Examples:
ghci> map fib [0..9] [0,1,1,2,3,5,8,13,21,34] ghci> map (fib . negate) [0..9] [0,1,-1,2,-3,5,-8,13,-21,34] ghci> length . show $ fib 10000000 2089877