Algorithmes de multiplications d'entiers et de matrices
Introduction
Depuis l'apparition des ordinateurs modernes, une quantité faramineuse de calcul a dû être effectué. 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 des 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
Définition
La complexité d'un algorithme, c'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 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 très fortement corrélé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é d'un algorithme se note É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}(f(x))} , 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 f(x)} la fonction qui adopte un comportement similaire à l'algorithme. Pour être plus précis, la 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}(f(x))} retranscrit mathématiquement 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 \exist } C > 0, É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 \exist } É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 } É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 \in \mathbb{N}} , É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} É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 } > n, É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)} ≤ C É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 \cdot } É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 }
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.
D'où le É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 efficace. 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
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 opérations.
On arrive assez facilement à la conclusion que pour faire notre produit, il va nous falloir faire n fois m opérations.
3) La multiplication karastuba
4) La multiplication toom-cook-3
II - Produit de matrices
(multiplication naive)