L’algorithme de Karatsuba

Soient Formule du chapitre 8, page 3 et Formule du chapitre 8, page 3 deux polynôFormule du chapitre 8, page 3eur produit.

Ils sont représentés par {a=[|a_{0};a_{1};...;a_{m}|],b=[|b_{0};b_{1};...;b_{n}|]} et {c=[|c_{0};c_{1};...;c_{m+n}\quad |].}

8.3.1 Algorithme naïf

On voit ici une fonction de multiplication na ̈ive de deux polynômes {A} et {B.} Tout le travail est fait dans la double boucle (on ne considère pas ici le coût de la création du tableau {c} en mémoire, et de son initialisation à 0) :

Il y a {2mn} opérations élémentaires (autant d’additions que de multiplications). Pour multiplier deux polynômes de {\mathbb{K}_{n-1}\quad [X],} il faut donc prévoir {2n^{2}} opérations élémentaires.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :