Algorithmes de multiplications d'entiers et de matrices
Introduction
Depuis l'apparition des ordinateurs modernes, une quantité faramineuse de calcul a dû être effectuée. Les progressions technologiques nous poussent à envisager la puissance de calcul comme une ressource qu'il faut optimiser dans les moindres détails. C'est ainsi que l'optimisation des algorithmes de calcul est devenue cruciale, surtout lorsqu'il nous faut effectuer des opérations sur de très grands entiers par exemple.
Objectif
L'objectif majeur de ce projet est de comprendre de manière plus approfondie ce qu'est la complexité algorithmique. Pour atteindre cet objectif, nous implémenterons plusieurs algorithmes de multiplication qui auront pour but de calculer le produit de grands entiers ou de matrices.
Point important : complexité
Définition
La complexité d'un algorithme est la quantité des ressources qu'il utilise en fonction de la taille des entrée qu'on lui demande de traiter. On peut par exemple se concentrer sur le temps qu'un algorithme prend pour renvoyer un résultat ou sur la mémoire dont il a besoin. Dans le cadre de notre projet, nous nous attarderons plus particulièrement sur la quantité de calcul effectuée en fonction de la taille des entrées, ce qui est par ailleurs fortement liée à la notion de temps. De manière générale, plus un algorithme doit faire de calcul, plus il est lent. (Attention, toutes les opérations arithmétiques de base ne se valent pas)
De manière plus familière, on dira que la complexité d'un algorithme pourrait s'apparenter à son comportement lorsqu'il doit traiter des données plus ou moins grandes. Chaque algorithme a une complexité, et on l'exprime par une fonction qui adopte un comportement similaire au nombre de calcul nécessaire en fonction de la taille des entrées.
Notation
La complexité réelle d'un algorithme peut être décrite par une fonction Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f(n)} représentant le nombre d'opérations effectuées en fonction de la taille Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle n} des données d'entrée.
Cependant, afin de simplifier l'étude de cette croissance, on utilise généralement une borne asymptotique notée Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{O}(g(n))} , où Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle g(n)} est une fonction ayant le même ordre de grandeur que Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f(n)} lorsque Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle n} devient grand.
On dit alors que :
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f(n)\in\mathcal{O}(g(n)) }
si et seulement s'il existe une constante Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle C>0} et un entier Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle n_0} tels que :
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \forall n\ge n_0,\ f(n)\le Cg(n) }
Cette notation Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{O}(g(n))} permettra de comparer beaucoup plus facilement les algorithmes entre eux.
Master Theorem
Afin de déterminer la complexité de certains algorithmes récursifs, nous utiliserons le "Master Theorem".
Ce théorème permet d'obtenir directement l'ordre de grandeur de nombreuses relations de récurrence apparaissant dans l'analyse d'algorithmes de type « diviser pour régner », comme l'algorithme de Karatsuba ou celui de Strassen.
La démonstration complète de ce théorème dépasse le cadre de notre projet et nécessite des connaissances mathématiques plus avancées. Nous l'utiliserons donc principalement comme un outil nous permettant de déterminer efficacement la complexité asymptotique des algorithmes étudiés.
Graphiques
Les complexités étant des fonctions, nous pouvons les représenter par un graphique qui affichera le temps d'exécution (ou nombre d'opérations) en fonction de la taille des entrées.
Ce graphique ci-contre compare les complexités en fonction de la taille des d'entrées.
On comprend ainsi que certaines complexités ne sont pas raisonnable dans la cadre de la multiplication de grands entiers.
C'est pourquoi l'étude de ces algorithmes s'avère nécessaire.
Exemple
L'algorithme naïf d'addition que nous avons tous appris à l'école a une complexité de Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{O}(n)} . Soit n la taille des nombres en entrée, l'algorithme doit faire environ n addition pour arriver au résultat demandé.
Comme le montre l'exemple ci-contre, 786 et 467 font 3 chiffres de long donc n sera de 3.
Il nous faudra 3 opérations pour additionner ces deux nombres.
C'est ainsi qu'avec une taille d'entrée n, l'algorithme de l'addition naïve va devoir faire n opérations.
Cette algorithme a donc une complexité Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f(n) = n} qui n'a pas besoin d'être approximée.
Ainsi sa complexité finale sera Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{O}(n)} .
Problématique
Le calcul du produit de deux entiers de manière naïve a une complexité de Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{O}(n^2)} , et celui de deux matrices une complexité de Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{O}(n^3)} . Afin de mieux comprendre ce qu'est la complexité algorithmique, nous devrons implémenter des algorithmes ayant le même objectif, mais étant plus efficaces. Ces algorithmes s'avèreront plus complexes mais devrait aboutir à un calcul plus rapide du produit demandé.
Nous séparerons notre wiki en deux grandes parties, la première concernera nos recherche sur la multiplication d'entiers, la deuxième sur la multiplication de matrices.
I - Produit d'entiers
Notre départ commence avec l'algorithme de multiplication d'entier naïf. En effet il s'agit de l'algorithme de multiplication le plus connu, et nous l'utiliserons comme référence pour le comparer aux futurs algorithmes plus efficaces. Intéressons nous à sa complexité.
1) Nos implémentations des grands entiers
Qui dit produit de grands entiers dit implémentation de grands entiers.
Dans le cadre de nos recherches, nous allons devoir implémenter des algorithmes qui vont manipuler des grands entiers.
Nous avons donc choisi de créer deux représentations différentes de ceux-ci (car nous travaillons sur différents langages de programmation), nous permettant à la fois une implémentation simplifié, mais aussi de nous rapprocher d'une implémentation bas niveau.
A) En python
En python, l'utilisation des "bytes" m'a grandement servi à comprendre comment les entiers étaient manipulés à bas niveau. En effet, un des objectifs secondaires de nos recherches était de manipuler des entiers directement avec leur formes stockées sur l'ordinateur, et non pas avec des int python. En effet l'utilisation des int python nous aurait permit de passer les étapes de retenues, de signes... D'autant plus que les bytes permettent de stocker un nombre en base 256, ce qui permet de visualiser plus facilement les grands entiers.
La forme finale de la représentation des grands entiers en python sera donc la suivante :
[ signe , bytes , bytes , (...) , bytes ]
Le signe est représenté par un entier, 1 si le nombre est positif, 0 sinon. Cette configuration rendra plus simple la gestion des signes.
B) En C++
En C++, pour avoir une représentation de grand entiers j'ai du définir ma propre structure pour m'affranchir de la limite de taille imposé par les entiers standards: (int32 ou int64). Pour cela, j'ai une structure qui possède l'équivalent d'un array de byte (ce qui nous permet d'être en base 256 au lieu de la base 10 habituelle), et pour traiter le signe j'utilise un booléen, ainsi en mémoire j'ai une structure de n*Octets + 1 octet en taille.
[ bytes , bytes , (...) , bytes ] [ signe ]
Le booléen prend 1 octet de place mais ne touche pas aux octets qui encode le grand entier. Cette configuration rendra plus simple la gestion des signes dans le cadre des multiplication.
2) La multiplication naïve
A) Fonctionnement
Dans le cas de la multiplication d'entiers, nous allons prendre deux nombres qui n'ont pas nécessairement la même longueur. Soit les nombre a et b, de longueur respective Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle n} et Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle m } .
Prenons deux nombres de longueur 3 et 2, et cherchons combien d'opérations l'algorithme de multiplication naïve va devoir faire pour nous renvoyer leur produit.
Dans un premier temps, on remarque que l'on va devoir multiplier chaque chiffre du nombre du haut par le chiffre des unités du bas, qui est 6. Cela va représenter Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle n} opérations. (6x5, 6x1 et 6x4)
Dans un deuxième temps nous constatons que nous allons devoir faire la même chose avec le chiffre des dizaines du nombre du bas. Cela nous ajoute de nouveau Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle n} opérations.
On arrive assez facilement à la conclusion que pour faire notre produit, il va nous falloir faire n fois m opérations.
Ainsi, la complexité de la multiplication naïve est Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{O}(n^2)} . Il est en de même avec la multiplication naïve récursive.
B) Graphique
Montrons maintenant sa courbe sur un graphique :
Les points noirs sont des repères pour que les autres courbes aient une forme cohérente.
La courbe rouge représente la complexité de la multiplication naïve.
On remarque que la courbe a un visuel très similaire à la fonction Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle f(x) = x^2}
3) La multiplication karastuba
A) Fonctionnement
L'algorithme de karatsuba est un algorithme récursif de type diviser pour régner.
L'idée générale de l'algorithme est de passer de 4 multiplication à 3. En effet ces opérations étant moins couteuses, il est préférable d'en ajouter si cela permet d'enlever des multiplications.
L'algorithme de multiplication naif récursif utilise la segmentation des facteurs en deux de manière successive.
Soit Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle x} et Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle y} deux facteurs, nous avons les égalités suivantes :
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle x = a \times B^{n/2} + b}
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle y = c \times B^{n/2} + d}
Avec Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle a} et Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle c} les premières moitiés des facteurs Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle x} et Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle y} , et Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle b} et Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle d} les dernières moitiés de ces facteurs ainsi que Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle B} la base d'écriture du nombre (Nous sommes en base 256 avec les bytes).
Cette présentation des deux facteurs de notre multiplication n'est que la résultante d'un découpage. Le Master Theorem nous montre que :
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle T(n) = 4T(n/2) + O(n)}
Puisque nous avons après découpage 4 entiers de longueur Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle n/2} .
Ainsi, ce découpage ne permet pas de gagner du temps d'après le Master Theorem.
Cependant, l'algorithme de Karatsuba réutilise ce principe en le modifiant, ce qui nous permet de baisser la complexité globale de la multiplication dans son entièreté.
Avec l'écriture ci-dessus des nombres Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle x} et Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle y} , on peut facilement en déduire l'égalité suivante :
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle x \times y = (ac) \times B^n + (ad + bc) \times B^{n/2} + bd}
On remarque 4 multiplications longues à faire dans cette expression. Les multiplications dont Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle B}
est l'un des facteurs sont très rapides puisqu'il s'agit de la base dans laquelle nous travaillons. De cela en résulte un décalage plutôt qu'un vrai calcul à faire.
Karatsuba développe une partie de cette expression pour pouvoir négocier une multiplication au prix d'additions et soustractions.
En effet, nous savons déjà que :
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle (a + b)(c + d) = ac + ad + bc + bd}
En manipulant l'égalité nous obtenons :
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle ad + bc = (a + b)(c + d) − ac − bd}
ac et bd ayant déjà été calculé précédemment, il nous reste uniquement la multiplication Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle (a + b)(c + d)} .
Nous venons ainsi de calculer Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle ad + bc} en seulement une multiplication. C'est la que repose le gain de temps de la méthode Karatsuba par rapport à la multiplication naïve.
B) Graphique
on a prit multi récursive
on voit que karatsuba en dessous de multi classique
meilleur complexité
4) La multiplication toom-cook-3
A) Fonctionnement
( A FAIRE )
B) Graphique
( A FAIRE )
5) La transformée de Fourier rapide
A) Fonctionnement
( A FAIRE )
B) Graphique
( A FAIRE )
II - Produit de matrices
1.1) naïve
La multiplication naïve de matrice requiert d'avoir des tailles de lignes/colonne semblable, ensuite pour chaque membre de la matrice résultat, on doit multiplier les composantes ligne de la première matrice par les composantes colonne de la deuxième et le tout sommé.
On en déduit la formule suivante:
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle C_{i,j} = \sum_{k=1}^{n} (A_{i,k} \times B_{k,j})}
Et visuellement:
On a donc un algorithme d'ordre de complexité Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle \mathcal{O}(g(n))}
1.2) naïve récursive
Dans un premier temps on doit découper nos deux matrices en quatres sous matrices de plus petite taille.
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle A = \begin{pmatrix} A_{11} & A_{12} \ A_{21} & A_{22} \end{pmatrix}}
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle B = \begin{pmatrix} B_{11} & B_{12} \ B_{21} & B_{22} \end{pmatrix}}
Ensuite on vient calculer la matrice résultat.
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle C_{11} = (A_{11} \times B_{11}) + (A_{12} \times B_{21})}
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle C_{12} = (A_{11} \times B_{12}) + (A_{12} \times B_{22})}
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle C_{21} = (A_{21} \times B_{11}) + (A_{22} \times B_{21})}
Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle C_{22} = (A_{21} \times B_{12}) + (A_{22} \times B_{22})}
Le côté récursif est utile que pour les matrices de tailles <= 32 (32 valeurs stockées dedans), si on est au dessus de cette taille alors on divisera à nouveau nos matrices en quatres. On aura 8 multiplications mais de plus petite taille au final.
2) strassen
A) Fonctionnement
Strassen consiste à définir 7 produits intermédiaires qui, par des jeux de sommes et de différences, permettent de reconstruire les quadrants de la matrice résultante. On passe ainsi d'une complexité de O(n^3) à environ O(n^2.81)
B) Graphique
( A FAIRE )
Conclusion
( A FAIRE )
Mentions
Le premier gif est le résultat du travail de 'Walké', licence ci-contre : https://fr.wikipedia.org/wiki/Fichier:Addition.gif
Sources
Pour karatsuba : https://www.youtube.com/watch?v=PZ2gdWdKHAA