## Fibonacci numbers

The Fibonacci numbers are defined recursively by the following difference equation:

\begin{equation}
\left\{
\begin{aligned}
    F_{n} & = F_{n-1} + F_{n-2} \\
    F_1 & = 1 \\
    F_0 & = 0 \\
\end{aligned}
\right.
\end{equation}

It is easy to compute the first few elements in the sequence:

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34 \cdots $
<!-- PELICAN_END_SUMMARY -->

## Derivation of the general formula

It is possible to derive a general formula for $F_n$ without computing all the previous numbers in the sequence. If a gemetric series (i.e. a series with a constant ratio between consecutive terms $r^n$) is to solve the difference equation, we must have

\begin{aligned}
    r^n = r^{n-1} + r^{n-2} \\
\end{aligned}

which is equivalent to

\begin{aligned}
    r^2 = r + 1 \\
\end{aligned}

This equation has two unique solutions
\begin{aligned}
    \varphi = & \frac{1 + \sqrt{5}}{2} \approx 1.61803\cdots \\
    \psi = & \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi} \approx -0.61803\cdots \\
\end{aligned}

In particular the larger root is known as the _golden ratio_
\begin{align}
\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\cdots
\end{align}

Now, since both roots solve the difference equation for Fibonacci numbers, any linear combination of the two sequences also solves it

\begin{aligned}
    a \left(\frac{1 + \sqrt{5}}{2}\right)^n + b \left(\frac{1 - \sqrt{5}}{2}\right)^n \\
\end{aligned}

It's not hard to see that all Fibonacci numbers must be of this general form because we can uniquely solve for $a$ and $b$ such that the initial conditions of $F_1 = 1$ and $F_0 = 0$ are met

\begin{equation}
\left\{
\begin{aligned}
    F_0 = 0 = a \left(\frac{1 + \sqrt{5}}{2}\right)^0 + b \left(\frac{1 - \sqrt{5}}{2}\right)^0 \\
    F_1 = 1 = a \left(\frac{1 + \sqrt{5}}{2}\right)^1 + b \left(\frac{1 - \sqrt{5}}{2}\right)^1 \\
\end{aligned}
\right.
\end{equation}

yielding

\begin{equation}
\left\{
\begin{aligned}
    a = \frac{1}{\sqrt{5}} \\
    b = \frac{-1}{\sqrt{5}} \\
\end{aligned}
\right.
\end{equation}

We have therefore derived the general formula for the $n$-th Fibonacci number

\begin{aligned}
    F_n = \frac{1}{\sqrt{5}} \left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1 - \sqrt{5}}{2}\right)^n \\
\end{aligned}

Since the second term has an absolute value smaller than $1$, we can see that the ratios of Fibonacci numbers converge to the golden ratio

\begin{aligned}
    \lim_{n \rightarrow \infty} \frac{F_n}{F_{n-1}} = \frac{1 + \sqrt{5}}{2}
\end{aligned}

## Various implementations in Python

Writing a function in Python that outputs the $n$-th Fibonacci number seems simple enough. However even in this simple case one should be aware of some of the computational subtleties in order to avoid common pitfalls and improve efficiency.

### Common pitfall #1: inefficient recursion

Here's a very straight-forward recursive implementation 


```python
import math
from __future__ import print_function
```


```python
def fib_recursive(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_recursive(n-1) + fib_recursive(n-2)
```


```python
print([fib_recursive(i) for i in range(20)])
```

    [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]


this seems to work fine, however the recursion overhead is actually very significant when $n$ is just slightly large. Here I'm computing $F_{34}$ and it takes more than 3 seconds! (on a 2013 model Macbook Air) 


```python
%timeit fib_recursive(34)
```

    1 loops, best of 3: 3.58 s per loop


The overhead incurred by creating a large number of stack frames is tremendous. Python by default does not perform what's known as tail recursion elimination http://stackoverflow.com/questions/13543019/why-is-recursion-in-python-so-slow, and therefore this is a very inefficient implemenation. In contrast, if we have an iterative implementation, the speed is dramatically faster


```python
def fib_iterative(n):
    a, b = 0, 1
    while n > 0:
        a, b = b, a + b
        n -= 1
    return a
```


```python
%timeit fib_iterative(34)
```

    100000 loops, best of 3: 4.59 µs per loop


Now, let's see if we can make it even faster by eliminating the loop altogether and just go straight to the general formula we derived earlier


```python
def fib_formula(n):
    golden_ratio = (1 + math.sqrt(5)) / 2
    val = (golden_ratio**n - (1 - golden_ratio)**n) / math.sqrt(5)
    return int(round(val))
```


```python
%timeit fib_formula(34)
```

    1000000 loops, best of 3: 1.36 µs per loop


Even faster, great! And since we are not looping anymore, we should expect to see the computation time to scale better as $n$ increases. That's indeed what we see:


```python
import pandas as pd
import numpy as np
```


```python
%matplotlib inline
import matplotlib.pyplot as plt
from IPython.core.pylabtools import figsize
figsize(15, 5)
```


```python
elapsed = {}
elapsed['iterative'] = {}
elapsed['formula'] = {}
for i in range(34):
    result = %timeit -n 10000 -q -o fib_iterative(i)
    elapsed['iterative'][i] = result.best
    result = %timeit -n 10000 -q -o fib_formula(i)
    elapsed['formula'][i] = result.best
```


```python
elapased_ms = pd.DataFrame(elapsed) * 1000
elapased_ms.plot(title='time taken to compute the n-th Fibonaccis number')
plt.ylabel('time taken (ms)')
plt.xlabel('n')
```

Indeed as we expect, the iterative approach scales linearly, while the formula approach is basically constant time.

However we need to be careful with using a numerical formula like this for getting integer results. 

### Common pitfall #2: numerical precision

Here we compare the actual values obtained by `fib_iterative()` and `fib_formula()`. Notice that it does not take a very large `n` for us to run into numerical precision issues.

When `n` is 71 we are starting to get different results from the two implementations!


```python
df = {}
df['iterative'] = {}
df['formula'] = {}
df['diff'] = {}

for i in range(100):
    df['iterative'][i] = fib_iterative(i)
    df['formula'][i] = fib_formula(i)
    df['diff'][i] = df['formula'][i] - df['iterative'][i]
df = pd.DataFrame(df, columns=['iterative', 'formula', 'diff'])
df.index.name = 'n-th Fibonacci'
df.ix[68:74]
```




<div style="max-height:1000px;max-width:1500px;overflow:auto;">
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>iterative</th>
      <th>formula</th>
      <th>diff</th>
    </tr>
    <tr>
      <th>n-th Fibonacci</th>
      <th></th>
      <th></th>
      <th></th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>68</th>
      <td>   72723460248141</td>
      <td>   72723460248141</td>
      <td> 0</td>
    </tr>
    <tr>
      <th>69</th>
      <td>  117669030460994</td>
      <td>  117669030460994</td>
      <td> 0</td>
    </tr>
    <tr>
      <th>70</th>
      <td>  190392490709135</td>
      <td>  190392490709135</td>
      <td> 0</td>
    </tr>
    <tr>
      <th>71</th>
      <td>  308061521170129</td>
      <td>  308061521170130</td>
      <td> 1</td>
    </tr>
    <tr>
      <th>72</th>
      <td>  498454011879264</td>
      <td>  498454011879265</td>
      <td> 1</td>
    </tr>
    <tr>
      <th>73</th>
      <td>  806515533049393</td>
      <td>  806515533049395</td>
      <td> 2</td>
    </tr>
    <tr>
      <th>74</th>
      <td> 1304969544928657</td>
      <td> 1304969544928660</td>
      <td> 3</td>
    </tr>
  </tbody>
</table>
</div>



You can see that `fib_iterative()` produces the correct result by eyeballing the sum of $F_{69}$ and $F_{70}$, while `fib_formual()` starts to have precision errors as the number gets larger. So, be mindful with precision issues when doing numerical computing. Here's a nice article on this topic http://www.codeproject.com/Articles/25294/Avoiding-Overflow-Underflow-and-Loss-of-Precision

Also notice that unlike C/C++, in Python there's technically no limit in the precision of its integer representation. In Python 2 any overflowing operation on `int` is automatically converted into `long`, and `long` has arbitrary precision. In Python 3 it is just `int`. More information on Python's arbitrary-precision integers can be found here  http://stackoverflow.com/questions/9860588/maximum-value-for-long-integer

e44db84d693f5c7af7794fe4b7a5ad73e04f9ae2
ipynb
Jupyter Notebook
blog/Fibonacci_numbers_in_python.ipynb
mortada/notebooks
12fd6a5fc1430efee63889f6cb709d8e94bde602
Apache-2.0
2015-06-16T23:48:03.000Z
2021-05-29T09:39:32.000Z
blog/Fibonacci_numbers_in_python.ipynb
mortada/notebooks
12fd6a5fc1430efee63889f6cb709d8e94bde602
Apache-2.0
blog/Fibonacci_numbers_in_python.ipynb
mortada/notebooks
12fd6a5fc1430efee63889f6cb709d8e94bde602
Apache-2.0
2015-06-18T17:55:08.000Z
2020-04-05T08:59:48.000Z
Qwen/Qwen-72B
1. YES
2. YES