Table des matières

The objective of this lab is to give an introduction to visualization with Matplotlib and scientific computing with Numpy. We'll implement a simple function with different programming methods, measure the performances of each and visualize the results.

## Classic programming methods

### Recursion

Develop a function

that computes the value of the n-th term of the Fibonacci sequence. This function must be **fibonacci_rec**(n)**recursive**. The expected results for the first values are: {$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181... $}

### Time analysis

The `timeit`

function of the package bearing the same name is used to measure the execution time of Python code. In the following example, `timeit`

returns the total time of 100 executions of the Python code to smooth the results.

Execution times may vary from machine to machine; you should expect an execution time of a few thousandths of a second. Try it.

from timeit import timeit timeit(lambda : fibonacci_rec(10), number=100)

We defined a function

that determines the execution time of a function for a sequence of values. **measure**()

When we measure the performances of

with different values of {$n$}, we should observe a high execution time for values
beyond {$n = 20$}.
**fibonacci**()

def measure(func, values, number=100): m = [] for i in values : m.append(timeit(lambda : func(i), number=number)) return m measure(fibonacci_rec, [1, 2, 3, 5, 10, 20, 25])

### Iteration

Develop a function

that computes the value of the n-th term of the Fibonacci sequence. This function must be **fibonacci_iter**(n)**iterative**.

Remark for advanced students : do not use memoization.

Measure the execution time of

. It should be significantly faster than the recursive version.
**fibonacci_iter**(n)

## Visualization

We'll now plot these values. We use the `pyplot`

module from the `matplotlib`

library.
The following instructions plot a series of points defined by two lists of coordinates `x`

and `y`

.

import matplotlib.pyplot as plt plt.plot(xvalues, yvalues, label="name for legend") plt.legend() plt.show()

The graph should always contain a title and a legend, have named axes, the scale of the y-axis must be logarithmic, the scale of the x-axis must start at 0. Here are some useful functions.

plt.yscale("log") plt.xlabel("Name") plt.ylabel("Name") plt.title("Name")

Be inclusive, don't forget color-blind people (about 1 in 20 people) and choose line styles that can be told apart without using colors. Line styles can be set with the following codes: ":", "-", "-." and "--".

plt.plot(xvalues, yvalues, "--", label="Dashed line")

### Put it all together

Define a function

that measures that execution time of **main**()

and **fibonacci_rec**()

, and
plots the performance curves.
**fibonacci_iter**()

## Alternative method

An alternative method to compute the Fibonacci sequence consists in using matrices. A matricial form of the Fibonacci sequence is given below:

{$$ \left( \begin{matrix} F_1 \\ F_2 \end{matrix} \right) = \left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right) * \left( \begin{matrix} F_0 \\ F_1 \end{matrix} \right) $$}

and in general:

{$$ \left( \begin{matrix} F_n \\ F_{n+1} \end{matrix} \right) = \left( \begin{matrix} 0 & 1 \\ 1 & 1 \end{matrix} \right)^n * \left( \begin{matrix} F_0 \\ F_1 \end{matrix} \right) $$}

We'll use `numpy`

to compute operations on matrices.
Here are some simple steps to help you.

Creation of matrices and vectors.

import numpy as np mat1 = np.array([[5,6],[10,3]]) vec = np.array([[9],[2]])

Access to one element.

mat1[1,0] # => 10

Some term-to-term operations.

mat2 = mat1 + mat1 # => mat2[i,j] = mat1[i, j] + mat1[i,j] mat3 = mat1 * 2 # => mat3[i,j] = mat1[i,j] * 2 ...

Some matrix operations.

mat4 = np.matmul(mat1, mat1) # matrix product mat5 = mat1 @ mat1 # abbreviated product syntax mat6 = np.linalg.matrix_power(mat1, 2) # mat1**2

Take a moment to familiarize yourself with `numpy`

matrix operations in a Python shell.

**WARNING**: you may already have used `np.matrix`

instead of `np.array`

. They work slightly differently. In particular, operations like `M ** 2`

or `M * vec`

are available for `np.matrix`

; it all seems very practical. **HOWEVER**, the `numpy`

documentation is very clear on this point, the `np.matrix`

object will be removed from the library soon, so you have to stop using them: "*It is no longer recommended to use this class, even for linear algebra. Instead use regular arrays. The class may be removed in the future*".

### Matrix

Develop a function

that computes the value of the n-th term of the Fibonacci sequence. This function must use **fibonacci_mat**(n)**numpy functions**.

Include this function in your performance analysis.

### Large values of {$n$}

Your recursive function is probably much slower than the other two variants. The execution time seems to increase exponentially with the value of {$n$}. And it does. Test your functions with larger values of {$n$}. Start with `range(1, 20, 2)`

, then `range(1, 30, 3)`

and so on until the execution time of

becomes too long.
**fibonacci_rec**

Test the three functions.

### The devil is in the detail

Compare the results of

and **fibonacci_iter**(93)

. Where does the problem come from?
**fibonacci_mat**(93)

### Well done

You have completed the first part of this lab. You studied the basics of visualization with `matplotlib`

and, for the first time, touched with hand the simplicity of matrix calculations with `numpy`

.
If you still have time, you may want to check the next following questions.

## Optional questions

The problem with the recursive function comes from the exponentially large number of recursive calls.
The function may be called many times with the same input value.
It is possible to work around this problem through **memoization**.
The rationale of memoization is to store the intermediate results in a dictionary
and make a recursive call only if the result of the call is not in the dictionary yet.

### Memoization

Modify the implementation of your recursive function to use memoization and compare its performances with the two other functions.

You can find out more on memoization here.

### Very large values of {$n$}

Up to what value of {$n$} can you compute results? It depends on your machine. Increase the measurement range, ex. from {$0$} to {$20,000$} with a step of {$1,000$}. One of the functions should generate an error message for too large values of {$n$}.

### In your opinion

- Why does

have an execution time which increases for small values of {$n$} and then seems to be constant?**fibonacci_mat**(n) - What does

error message means for large values of {$n$}?**fibonacci_rec**(n)

### Try the matrix computation your way

Since matrix computation with Numpy generates overflows, you can implement your own method using lists of native Python integer numbers. You'll need a function to compute the product of matrices (matrices will be represented as lists of lists), and a fast exponentiation function.