# Fibonacci numbers (Python)

### From LiteratePrograms

**Other implementations**: ALGOL 68 | Alice ML | bc | C | C Plus Plus templates | dc | E | Eiffel | Erlang | Forth | FORTRAN | Haskell | Hume | Icon | Java | JavaScript | Lisp | Logo | Lua | Mercury | OCaml | occam | Oz | Pascal | PIR | PostScript |**Python**| Ruby | Scala | Scheme | Sed | sh | sh, iterative | Smalltalk | T-SQL | 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

- 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>>=deffib(n):ifn == 0:return0elifn == 1:return1else:returnfib(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 Φ^{n}, 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>>=deffib(n):ifnotninmemo: memo[n] = fib(n-1) + fib(n-2)returnmemo[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 *n*th Fibonacci number in only *n* steps, we can also start with 0 and 1 and iteratively add up items *n* times:

<<fibonacci_iteration.py>>=deffib(n): a, b = 0, 1foriinrange(n): a, b = b, a + breturna

## Generator

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

<<fibonacci_generator.py>>=deffib(): a, b = 0, 1while1: 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 *n*th Fibonacci number with Binet's formula

All sequences defined by linear recurrence have an associated closed-form expression for the *n*th 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) / 2deffib(n):returnint(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>>=frommathimportlogdeffibinv(f):iff < 2:returnfreturnint(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 *n*th 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 *n*th 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>>=defmul(A, B): a, b, c = A d, e, f = Breturna*d + b*e, a*e + b*f, b*e + c*fdefpow(A, n):ifn == 1:returnAifn & 1 == 0:returnpow(mul(A, A), n//2)else:returnmul(A, pow(mul(A, A), (n-1)//2))deffib(n):ifn < 2:returnnreturnpow((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*_{2n} = *L*_{n}*F*_{n}. Similar , and .

<<fibonacci_LF.py>>=defpowLF(n):ifn == 1:return(1, 1) L, F = powLF(n//2) L, F = (L**2 + 5*F**2) >> 1, L*Fifn & 1:return((L + 5*F)>>1, (L + F) >>1)else:return(L, F)deffib(n):returnpowLF(n)[1]

Notes:

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

deffib(n):ifn & 1:returnpowLF(n)[1]else: L, F = powLF(n // 2)returnL * 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 http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF), we can iterate, for large numbers, very few times (for F1000 we only need 22 iterations)

<<fibonacci_ewd.py>>=fibs ={0: 0, 1: 1}deffib(n):ifninfibs:returnfibs[n]ifn % 2 == 0: fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2)returnfibs[n]else: fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n+1) / 2) ** 2)returnfibs[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 |