Fibonacci numbers (Python)

From LiteratePrograms

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

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.

Recursion

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

<<fibonacci_recursive.py>>=
def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

Testing:

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

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 Φⁿ, where Φ is the golden ratio). Interestingly, when computing fib(n), the for all 1<k<n fib(k) is called fib(n-k) times, but fib(0) is called fib(n-2) times.

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:

<<fibonacci_memo.py>>=
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).

<<fibonacci_memo.py>>=
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 708449696358523830149 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)
354224848179261915075

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:

<<fibonacci_iteration.py>>=
def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

Generator

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

<<fibonacci_generator.py>>=
def fib():
    a, b = 0, 1
    while 1:
        yield a
        a, b = b, a + b

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

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)

where is the golden ratio,

This can be implemented straightforwardly:

<<fibonacci_binet.py>>=
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 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)):

<<fibonacci_binet.py>>=
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.

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

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

<<fibonacci_matrix.py>>=
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]

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 as , where $L n$ is $n$ -th Lucas number and $F n$ is $n$ -th Fibonacci number. It is easy to obtain formulas necessary for exponentiation by squaring. For example: . Therefore , $F 2 n = L n F n$ . Similar , and .

<<fibonacci_LF.py>>=
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)
    else:
        return (L, F)
def fib(n):
    return powLF(n)[1]

Notes:

(1) The code can be imporved: it is not necessary to calculate $L n$ on the last step.

def fib(n):
    if n & 1:
        return powLF(n)[1]
    else:
        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.

Quick exact computation of large individual Fibonacci numbers (third strike)

Using a method developed by E. W. Dijkstra (found at), we can iterate, for large numbers, very few times (for F1000 we only need 22 iterations)

<<fibonacci_ewd.py>>=
fibs = {0: 0, 1: 1}
def fib(n):
    if n in fibs: return fibs[n]
    if n % 2 == 0:
        fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2)
        return fibs[n]
    else:
        fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n+1) / 2) ** 2)
        return fibs[n]

At the expense of immediate legibility, we can compute Fibonacci numbers way faster than naive methods. Uses caching of results both for speed and to define starting values.

Download code

Retrieved from "http://literateprograms.org/Fibonacci_numbers_%28Python%29"

Categories: Fibonacci numbers | Programming language:Python | Environment:Portable