Fibonacci numbers (Python)

From LiteratePrograms
Jump to: navigation, search
Other implementations: bc | C | C Plus Plus templates | dc | E | Forth | FORTRAN | Haskell | Icon | Java | JavaScript | Lisp | Lua | occam | Oz | PIR | Prolog | Python | Sed | sh | sh, iterative | Visual Basic .NET

The Fibonacci numbers are the integer sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, ..., in which each item is formed by adding the previous two. The sequence can be defined recursively by

 F(n) =
   0             & n = 0 \\
   1             & n = 1 \\
   F(n-1)+F(n-2) & n > 1 \\
  \end{cases} .

Fibonacci number programs that implement this definition directly are often used as introductory examples of recursion. However, many other algorithms for calculating (or making use of) Fibonacci numbers also exist.


[edit] Recursion

The recursive definition can be translated directly into Python as follows:

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
        return fib(n-1) + fib(n-2)


>>> fib(0), fib(1), fib(2), fib(3)
(0, 1, 1, 2)
>>> fib(7)

[edit] Recursion with memoization

Although the recursive implementation given above is elegant and close to the mathematical definition, it is not very practical. Calculating fib(n) requires calculating two smaller Fibonacci numbers, which in turn require two additional recursive calls each, and so on until all branches reach 1. As a consequence, the time required to calculate fib(n) is exponential in n (it is about Φn, where Φ is the golden ratio). To remedy this, we can employ memoization to cache previous computations.

The memoization cache is a dictionary consisting of entries composed of a key n and a corresponding value fib(n). We initialize the dictionary with the first two Fibonacci numbers:

memo = {0:0, 1:1}

The memoized fib function recursively computes and stores the value of fib(n) if it hasn't been previously stored in the memo dictionary. Otherwise it simply returns the memoized value of fib(n).

def fib(n):
    if not n in memo:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

Computing fib(100) with the simple recursive version requires 1146295688027634168201 function calls, which would take longer than the age of the universe to execute even though the stack depth would never exceed 100. With the memoized version, the 100th Fibonacci number can be found in no time:

>>> fib(100)

[edit] Iteration

To calculate the nth Fibonacci number in only n steps, we can also start with 0 and 1 and iteratively add up items n times:

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

[edit] Generator

We can also construct a generator that calculates and yields the Fibonacci numbers one at a time:

def fib():
    a, b = 0, 1
    while 1:
        yield a
        a, b = b, a + b
>>> a = fib()
>>> for i in range(10):
...     print,
1 1 2 3 5 8 13 21 34 55

[edit] Direct computation of the nth Fibonacci number with Binet's formula

All sequences defined by linear recurrence have an associated closed-form expression for the nth number. The Fibonacci numbers in particular are given by Binet's formula (for Jacques Philippe Marie Binet)

F\left(n\right) = {{\varphi^n-(1-\varphi)^n} \over {\sqrt 5}}

where \varphi is the golden ratio,

\varphi = \frac{1 + \sqrt{5}}{2}.

This can be implemented straightforwardly:

phi = (1 + 5**0.5) / 2

def fib(n):
    return int(round((phi**n - (1-phi)**n) / 5**0.5))

Because of floating-point rounding errors, this will however only give the right result for n < 70.

Binet's formula can be inverted by ignoring the (1-\varphi)^n term, which disappears for large n. We can therefore define the inverse Fibonacci function that, when given F(n), returns n (ignoring that F(1) = F(2)):

from math import log

def fibinv(f):
    if f < 2:
        return f
    return int(round(log(f * 5**0.5) / log(phi)))

Here rounding is used to our advantage: it removes the error introduced by our modification to Binet's formula. The function will in fact return the right answer when given any Fibonacci number that can be stored as an exact integer in the computer's memory. On the other hand, it does not verify that the given number actually is a Fibonacci number; inputting a large Fibonacci number or any number close to it will give the same result. This may be useful, for example to find the Fibonacci number closest to a given number.

[edit] Quick exact computation of large individual Fibonacci numbers

There are efficient ways to calculate the nth Fibonacci number exactly without first calculating all its predecessors. One way to do so is to utilize the matrix identity

\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n =
       \begin{pmatrix} F\left(n+1\right) & F \left(n\right) \\
                       F\left(n\right)   & F \left(n-1\right) \end{pmatrix}

and employing exponentiation by squaring to find the nth power of the left-hand matrix. We here represent a 2-by-2 matrix A as the 3-tuple (a, b, c) where

A = \begin{pmatrix} a & b \\ b & c \end{pmatrix}.
def mul(A, B):
    a, b, c = A
    d, e, f = B
    return a*d + b*e, a*e + b*f, b*e + c*f

def pow(A, n):
    if n == 1:     return A
    if n & 1 == 0: return pow(mul(A, A), n//2)
    else:          return mul(A, pow(mul(A, A), (n-1)//2))

def fib(n):
    if n < 2: return n
    return pow((1,1,0), n-1)[0]

[edit] Quick exact computation of large individual Fibonacci numbers (second take)

Our next approach to quick computation of large Fibonacci number is based on representation of \varphi^n as \varphi^n = \frac{L_n + F_n \sqrt5}{2}, where Ln is n-th Lucas number and Fn is n-th Fibonacci number. It is easy to obtain formulas necessary for exponentiation by squaring. For example: \frac{L_{2n} + F_{2n} \sqrt5}{2} = \varphi^{2n} = (\varphi^{n})^2 = \left(\frac{L_{n} + F_{n} \sqrt5}{2}\right)^2. Therefore L_{2n} = \frac{L_n^2+5F_n^2}{2}, F2n = LnFn. Similar L_{n+1} = \frac{L_n + 5 F_n}{2}, and F_{n+1} = \frac{L_n + F_n}{2}.

def powLF(n):
    if n == 1:     return (1, 1)
    L, F = powLF(n//2)
    L, F = (L**2 + 5*F**2) >> 1, L*F
    if n & 1:
        return ((L + 5*F)>>1, (L + F) >>1)
        return (L, F)

def fib(n):
    return powLF(n)[1]


(1) The code can be improved: it is not necessary to calculate Ln on the last step.

def fib(n):
    if n & 1:
        return powLF(n)[1]
        L, F = powLF(n // 2)
        return L * F

(2) The choice of power (**2) over multiplication is based on experiments (this way program is 10% faster).

(3) It is obvious how to rework this algorithm to the iterative one at the expense of its clarity.

Download code