Algorithmes de multiplications d'entiers et de matrices
Introduction
Depuis l'apparition des ordinateurs modernes, une quantité faramineuse de calculs 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ées 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 étroitement 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 calculs nécessaires 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 entiers.
C'est ainsi qu'avec une taille d'entrée n, l'algorithme de l'addition naïve va devoir faire n opérations.
Cet 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 É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} 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 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 }
Cette 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 karatsuba
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.
Ainsi nous vérifions donc ce que le Master Theorem prouve, c'est à dire que la complexité 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})}
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:
Résultat
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 à É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 } 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.
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_n a_{n-1} (...) a_1 a_0}
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 en réalité 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 \times 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_0 + a_1 \times 10 + \dots + a_{n-1}10^{n-1} + a_n10^n }
Nous venons ainsi d'écrire notre nombre sous la forme d'un polynôme unique. Pour nous permettre d'évaluer en un nombre suffisant de points, nous allons devoir ajouter des 0 pour la récursion. Il nous faudra ajouter assez de 0 pour atteindre la prochaine puissance de 2 qui sera supérieure ou égale à É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 2n + 1} . L'ajout de 0 ne change pas le nombre car É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 0 \times x^n} n'ajoute pas de coefficient.
Cet algorithme est récursif et va segmenter en deux parties nos polynômes à chaque récursion. D'un coté les indice pairs et d'un coté les impaires.
Ainsi prenons les nombres 1234 et 5678, ces nombres sont respectivement représentés par les polynômes É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) = 4 + 3x + 2x^2 + x^3 } 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 P(x) = 8 + 7x + 6x^2 + 5^3 } . Ce sont des polynômes de degré 3, ainsi leur produit donnera lieu à un polynôme de degré 6. Il nous faudra donc au minimum 7 points d'évaluation pour retrouve ce produit. De ce fait, en les représentant de la manière 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 [4, 3, 2, 1, 0, 0, 0, 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 [8, 7, 6, 5, 0, 0, 0, 0]}
Nous aurons assez de récursions possible pour les évaluer en un nombre suffisant de points différents car nous auront 3 récursions à faire pour atteindre notre cas de base. A chaque récursion, nous allons diviser nos polynômes en deux parties ce qui nous fait 8 feuilles à la dernière récursion.
En effet à chaque étape de la récursion nous allons séparer nos polynômes en deux 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 P(x)=P_{\text{pair}}(x^2) + x \cdot P_{\text{impair}}(x^2)}
Durant les récursions, nous segmentons les polynômes mais ne les évaluons pas. C'est à la remonté des récursions que nous allons réellement évaluer nos polynômes. Lorsque l'on atteint notre cas de base, c'est à dire des polynômes de degré 0, nous remarquons qu'ils sont constants, nous n'avons donc pas besoin de les évaluer. En effet, peut importe le point en lequel nous voudrons l'évaluer, le polynôme renverra la constante. Nous la renvoyons donc seule. Ensuite commence la remontée des récursions. A l'étape 1 de notre remontée nous allons reformer le polynôme précédemment séparé pour obtenir un polynôme de degré 1. Puis, nous évaluons ce polynôme avec les racines seconde de l'unité. Nous faisons à nouveau remonté les évaluations et recombinons à nouveau le polynôme qui sera ainsi de degré 2. Nous l'évaluons maintenant avec les racines 4eme de l'unité. A chaque évaluation, nous réutilisons les résultats précédents, cela nous est permit par les racines de l'unité qui ont une structure récursive exploitable.
Finalement, nous arrivons à la fin de notre FFT, avec une représentation fréquentielle de 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(W_0), P(W_1), (...), P(W_n-1), P(W_n)] }
Cette représentation fréquentielle n'est autre que les évaluations du polynôme P aux racines nièmes de l'unité. Nous avons donc maintenant au minimum É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 2n+1} évaluations des polynômes facteurs. Il nous faut maintenant trouver les évaluations du produit final, c'est à dire les évaluations concernant le polynôme qui sera issue de la multiplication. On pourra ainsi le retrouver.
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 C} un polynome 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 \times B } , alors on a :
É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) \times B(x) }
Ainsi on en déduit 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(W_n^k) = A(W_n^k) \times B(W_n^k) }
On comprend donc 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 FFT(C) = FFT(A) \times FFT(B)}
Il faut préciser que l'on fait le produit de FFT(A) et FFT(B) terme à terme, soit évaluation par évaluation.
Une fois en possession 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 FFT(C)} , qui n'est autre que l'évaluation de notre polynôme final en un nombre suffisant de points pour le retrouver, nous pouvons faire l'É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 IFFT(FFT(C))} , qui va nous permettre de retrouver les coefficients de notre polynôme en faisant l'exacte inverse de la FFT.
Une fois les coefficients retrouvés, il nous suffit de gérer les retenues, et nous retrouvons un entier de 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 a_0 a_1 (...) a_{n-1} a_n}
B) Graphique
Intéressons nous maintenant à la complexité de l'algorithme utilisant la transformée de Fourier rapide. On sait que l'algorithme passe par 5 étapes importantes :
- Etape 1 : Ecrire les deux facteurs sous la forme de polynômes
- Etape 2 : Effectuer la É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 FFT} des deux polynômes
- Etape 3 : Faire le produit terme à terme des É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 FFT} obtenues
- Etape 4 : Faire l'É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 IFFT} du produit
- Etape 5 : Gérer les retenues et écrire le nombre qui en découle
Or, parmi toutes ces étapes, certaines sont négligeable comme l'étape 1 et 5.
Pour connaitre la complexité de l'algorithme, additionnons les complexités des étapes restantes :
Une É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 FFT} 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\times logn)} car elle fait É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} évaluation 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 log(n)} récursions. Dans le cadre de notre algorithme, nous devons faire la É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 FFT} de nos deux facteurs. 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 2\times \mathcal{O}(n\times logn)} .
Pour le produit terme à terme, nous faisons naturellement É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.
Pour finir, l'É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 IFFT} a la même complexité que la É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 FFT} . Dans le cadre de notre algorithme nous l'emploierons qu'une seule fois, ce qui fait 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\times logn)} .
Après addition de toutes ces complexités, nous obtenons la complexité réelle 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 3\mathcal{O}(n\times logn) + \mathcal{O}(n)} .
D'après le Master Theorem, nous avons 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 f(n) = 3(n\times logn)+n } , cherchons É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))} :
Nous pouvons ignorer les expressions linéaires ainsi que les constantes multiplicatrices, nous obtenons 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 \mathcal{O}(g(n)) = \mathcal{O}(n \times log n)} .
Ce graphique ci-contre ne provient pas du fruit de nos recherches personnelles mais illustre bien la comparaison entre la complexité de la FFT et des autres algorithmes.
On remarque que la FFT est très efficace et devance de loin les autres algorithmes en terme de complexité.
Les algorithmes les plus efficaces pour calculer le produit de grands entiers reposent aujourd'hui sur des variantes de la transformée de Fourier rapide.
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
L'étude de ces algorithmes de multiplication nous a clairement montré l'évolution de la complexité algorithmique permettant de gagner en efficacité lorsque la taille des données augmente.
La multiplication classiqe, en É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)} , résulte d'une approche naïve qui devient rapidement inefficace pour les grands entiers ou les grandes matrices. L'algorithme de Karatsuba nous montre qu'organiser de manière intelligente ses calculs algébrique permet parfois de gagner beaucoup de multiplications, et donc de temps. Nous avons ainsi réussi à passer d'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)} à É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^{log_2(3)})} , soit environ É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})} .
Des méthodes encore plus avancées comme utilise l'algorithme de Toom-Cook-3 continue dans cette idées de divisions d'entiers en blocs plus petits, tandis que la transformée de Fourier rapide change complètement de point de vue. En effet la FFT n'utilise pas la représentation classique des entiers mais fait appel à une vision polynomiale, ce qui transforme la convolution classique en multiplication terme à terme, ce qui lui permet d'atteindre 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 \times log n)} .
Dans le cas des matrices, les mêmes logiques apparaissent comme par exemple avec l'algorithme de Strassen qui se rapproche très fortement de Karatsuba en combinant de manière astucieuse les parties d'entiers qui avaient été précédemment découpée.
On remarque néanmoins que la majorité des algorithmes efficaces s'orientent vers une approche récursive et non itérative. Néanmoins, nous avons pu trouver certaines de ces implémentations (comme par exemple la FFT) en itérative.
Avec ces recherches, nous comprenons que la réorganisations des calculs algébriques peuvent aider à gagner en complexité mais que pour faire de réels progrès, il nous faudra surement changer notre point de vue une nouvelle fois, et aborder le problème sous un angle nouveau comme le font dors et déjà les algorithmes les plus performants.
Mentions
Le premier gif est le résultat du travail de 'Walké', licence ci-contre : https://fr.wikipedia.org/wiki/Fichier:Addition.gif
Utilisation du site de production graphique "Desmos" : https://www.desmos.com/calculator?lang=fr
Sources
Pour karatsuba :
Pour mieux comprendre la FFT, nous avons utilisé plusieurs sources d'informations :