6. Euklidean algorithm

Deadline: 2022-03-29 24:00

The Euclidean algorithm, or Euclid's algorithm, is an efficient method for computing the greatest common divisor of two numbers. If the input $a, b \in \mathbb{Z}^+$ are two binary numbers, then the length of input is $O(\log a + \log b)$, and the Euclidean algorithm calculate the value $\mathop{\mathrm{gcd}}(a, b)$ in at most $O(\log a + \log b)$ steps.
In the file euklidean.py a part of a program is given which plot the heat map of the function $\log a + \log b$ on the $(a, b)$ coordinate-plane with the matplotlib.pyplot Python package (see the tutorial). The values of $a$ and $b$ are integer numbers between $1$ and $100$. The heat map shows the value of the numbers with the colors of the rainbow from violet to yellow.
Modify the program to show the running of the euclidean algorithm! Plot three heat maps side by side in a window similar to one of the following. With the new version of matplotlib installed on your computer the result of the home work looks like this:
$heatmap.png$

The following functions should be shown on the heat maps:
1. The first heat map shows the function $\log_2 a + \log_2 b$, which is generated by the program euklidean.py.
2. The second heat map shows the number of steps of the Euclidean algorithm on each pair $(a, b)$. On the number of steps we mean: how many divisions with reminder made on $(a_i, b_i)$ pairs or decide to stop.
3. The third heat map shows the value $\mathop{\mathrm{gcd}}(a, b)$.
The subplot function of matplotlib.pyplot package can be used to display multiple figures. The argument of this function is a 3-digit number $nmk$, where the $n$ is the number of rows, $m$ is the number of columns of subfigures on the canvas. The third $k$ is the index of the subfigure, which starts at 1 in the upper left corner and increases to the right. For example
```
plt.subplot(132)
    
```
means that the canvas has 3 subfigures in a row, and all the results of the function calls of plt appear on the second subfigure.