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 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.
Ils sont tous sur l'axe des abscisses.
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}
La courbe rouge représente la complexité de la multiplication naïve récursive.
Elle sera utilisé pour comparer les complexités entre algorithmes car, comme tous récursifs, elle a été codé avec les mêmes biais d'implémentation qu'eux.
Théoriquement les deux courbes ci-contre ont la même complexité, mais encore une fois, notre implémentation n'est pas parfaitement optimale et donc ne respecte pas de manière minutieuse le Master Theorem.
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.
En effet, l'algorithme n'effectuera alors plus que 3 multiplications :
É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 ac}
É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 bd}
É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)}
La relation de récurrence devient donc :
É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)=3T(n/2)+O(n)}
Et le Master Theorem nous dit 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)\in O(n^{\log_2(3)})}
Or É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 \log_2(3)\approx 1.585} , donc la complexité de l'algorithme de Karatsuba est 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^{1.585})} . Ce qui est bien plus efficace que la multiplication classique, surtout lorsque les facteurs deviennent très grands.
B) Graphique
Sur le graphique ci-contre nous avons utilisé la courbe de la multiplication naïve récursive (rouge) à titre de comparaison.
On remarque graphiquement que Karatsuba (jaune) prend moins de temps à chaque calcul de produit.
On en déduit donc expérimentalement que Karatsuba à une meilleure complexité que la multiplication naïve.
Cela nous vérifions donc ce que le Master Theorem prouve, c'est à dire que la complexité de karatsuba est de
4) La multiplication toom-cook-3
A) Fonctionnement
L'objectif est de diviser les grands entiers X et Y en trois blocs de taille égale k. On les traite alors comme des polynômes de degré 2:
É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 P(z) = X_2 \cdot z^2 + X_1 \cdot z + X_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 Q(z) = Y_2 \cdot z^2 + Y_1 \cdot z + Y_0}
On choisit 5 points distincts pour évaluer nos polynômes. Ce choix de 5 points est crucial car le produit de deux polynômes de degré 2 est un polynôme de degré 4, qui nécessite 5 points pour être défini. Les points standards sont :
P(0) = X0 P(1) = X0 + X1 + X2 P(-1) = X0 - X1 + X2 P(2) = X0 + 2*X1 + 4*X2 P(inf) = X2
(On procède de manière similaire pour Q.)
Ensuite nous multiplions récursivement chaque points de P et de Q ensemble. On effectue ainsi 5 multiplications de nombres plus petits au lieu des 9 multiplications requises par la méthode classique.
Après, nous effectuons une interpolation, cela permet de retrouver les 5 coefficients (w_0, w_1, w_2, w_3, w_4) du polynôme produit R(z) à partir des valeurs évaluées calculées précédemment. On résout un système d'équations linéaires : É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 R(z) = w_4 z^4 + w_3 z^3 + w_2 z^2 + w_1 z + w_0 } Finalement nous pouvons recomposer notre grand entier en positionnant les coefficients w_i aux bons rangs (en les décalant) et à gérer les retenues lors de l'addition finale:
É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 Résultat = w_4 B^{4k} + w_3 B^{3k} + w_2 B^{2k} + w_1 B^k + w_0}
B) Graphique
on a reprit multi récursive (rouge)
on voit que Toom (vert) en dessous de karatsuba (jaune) en dessous de multi classique (rouge)
meilleur complexité
5) La transformée de Fourier rapide
A) Fonctionnement
La transformation de Fourier rapide étant plus complexe que les autres algorithmes, nous allons essayer d'expliquer son fonctionnement malgré ne pas avoir réussi à l'implémenter.
Il faut comprendre que cet algorithme va considérer les facteurs comme des polynômes.
D'après le théorème de l'unisolvance, il n'existe qu'un seul polynôme de degré inférieur ou égal à n défini par É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 + 1} points distincts. Cela implique non seulement que nous pouvons représenter chaque entier par un polynôme, mais également que si nous pouvons retrouver É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 + m + 1} points (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 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} la longueur des facteurs) du polynômes issue du produit entre deux facteurs, nous pourrons le retrouver.
Les "points" ne sont autre que des évaluations Dans cet algorithmes nous allons également utiliser une propriété qui est que si A, B et C trois polynômes tel 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 C = A ⋅ B} , alors É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(x) = A(x) ⋅ B(x)} .
Ce résultat est très puissant puisque pour retrouver notre produit, il nous faut évaluer nos facteurs sur É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 + m + 1 }
.
L'objectif est donc de représenter nos deux grands entier facteurs par deux polynômes.
Soit un entier quelconque, de forme :
É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_0 a_1 (...) a_{n-1} a_n}
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_i} , un chiffre composant le nombre en base 10, qui vaut dans le nombre É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_i} fois É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 10^i} . On peut ainsi l'écrire sous la forme :
É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 P(x) = a_0 + a_1x + a_2x^2 + \dots + a_{n-1}x^{n-1} + a_nx^n }
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 x = 10} car nous sommes en base 10, 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 P(10)=a_n10^n+a_{n-1}10^{n-1}+\dots+a_1 10+a_0}
Nous venons ainsi d'écrire notre nombre sous la forme d'un polynôme unique.
B) Graphique
( A FAIRE ) (on aura pas de courbe par contre)
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
On voit bien la différence de complexité sur la multiplication de grande matrice entre l'approche naïve et l'approche récursive qui est beaucoup plus rapide.
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
Pour mieux comprendre la FFT, nous avons utilisé plusieurs sources d'informations :
https://www.youtube.com/watch?v=h7apO7q16V0&list=WL&index=1&t=886s