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 $
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}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.
Here's a very straight-forward recursive implementation
In [1]:
import math
from __future__ import print_function
In [2]:
def fib_recursive(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib_recursive(n-1) + fib_recursive(n-2)
In [3]:
print([fib_recursive(i) for i in range(20)])
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)
In [4]:
%timeit fib_recursive(34)
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
In [5]:
def fib_iterative(n):
a, b = 0, 1
while n > 0:
a, b = b, a + b
n -= 1
return a
In [6]:
%timeit fib_iterative(34)
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
In [7]:
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))
In [8]:
%timeit fib_formula(34)
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:
In [9]:
import pandas as pd
import numpy as np
In [10]:
%matplotlib inline
import matplotlib.pyplot as plt
from IPython.core.pylabtools import figsize
figsize(15, 5)
In [11]:
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
In [12]:
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')
Out[12]:
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.
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!
In [13]:
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]
Out[13]:
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