[PDF] [PDF] Multiplication rapide : Karatsuba et FFT

[PDF] Multiplication de polynômes

Soient les deux polynômes 7y3 + 9y2 + y +5et2y2 + 4y + 2 • Pour les multiplier il suffit de placer les polynômes comme si nous allions les addition- ner: 7y3 +

[PDF] Multiplication rapide de polynômes - École normale supérieure de

L'objectif de ce sujet est d'étudier divers algorithmes de multiplication de polynômes ainsi que leur complexité en fonction du nombre de termes des polynômes 

[PDF] Multiplication de polynômes - GRAAL

▷ Question 5 En utilisant la fonction précédente, écrivez une fonction multiplication qui calcule le pro- duit de deux polynômes multiplication : polynome −> 

[PDF] Multiplication rapide de polynômes et de matrices 1 - Normale Sup

9 avr 2008 · qui calculent respectivement la somme de deux polynômes, la multiplication d'un polynôme par un scalaire, et la différence de deux polynômes

[PDF] Multiplication rapide : Karatsuba et FFT

Nous nous limitons ici aux polynômes, mais ces méthodes conduisent également à des algorithmes de multiplication rapide des entiers L'algorithme de 

[PDF] Multiplication de polynômes poly_mul

7 nov 2012 · multiplication de polynômes, ainsi qu'une fonction qui affiche un polynôme void poly_add ( const double complex ∗P, int degP , const double 

[PDF] Polynômes - Université de Sherbrooke

14 août 2018 · Plan du chapitre 1 Définitions 2 Addition et soustraction de polynômes 3 Multiplication de polynômes 4 Division de polynômes 5 Références

[PDF] Multiplication de polynômes : Karatsuba, FFT - Institut de

On propose ici d'écrire des procédures de multiplication de polynômes Chacune On désire calculer le produit de deux polynômes P, Q ∈ R[X] de degrés < n,

[PDF] Multiplication et addition de fractions

[PDF] multiplication et division

[PDF] Multiplication et division de décimaux relatifs

[PDF] multiplication et division de fraction 4eme

[PDF] multiplication et division de fraction exercices

[PDF] Multiplication et division de nombres relatifs

[PDF] multiplication et division des nombres relatifs 4ème exercices

[PDF] Multiplication et Division en écriture fractionnaire

[PDF] multiplication et division exercices

[PDF] multiplication et division jeux

[PDF] multiplication et fractions avec ses étapes

[PDF] multiplication facts 0-12

[PDF] multiplication facts 1-12 printable

[PDF] multiplication nombre relatif

[PDF] multiplication nombre relatif 4eme

Multiplication rapide de polynômes

Épreuve pratique d"algorithmique et de programmation Concours commun des Écoles normales supérieures

Durée de l"épreuve: 3 heures 30 minutes

Juin/Juillet 2014ATTENTION !

0Important.

Sur votre table est indiqué un numérou0qui servira d"entrée à vos programmes. Les

réponses attendues sont généralement courtes et doivent être données sur la fiche réponse

fournie à la fin du sujet. À la fin du sujet, vous trouverez en faitdeux fiches réponses. La

première est un exemple des réponses attendues pour uneu0particulier (précisé sur cette même fiche et que nous notons avec un tilde pour éviter toute confusion!). Cette fiche

est destinée à vous aider à vérifier le résultat de vos programmes en les testant aveceu0

au lieu deu0. Vous indiquerez vos réponses (correspondant àvotreu0) sur la seconde et vous la remettrez à l"examinateur à la fin de l"épreuve. En ce qui concerne la partie orale de l"examen, lorsque la description d"un algorithme est demandée, vous devez présenter son fonctionnement de façon schématique, courte et Quand on demande la complexité en temps ou en mémoire d"un algorithme en fonction d"un paramètren, on demande l"ordre de grandeur en fonction du paramètre, par exemple:

O(n2),O(nlogn),...

Il est recommandé de commencer par lancer vos programmes sur de petites valeurs des paramètres et detester vos programmes sur des petits exemples que vous aurez résolus préalablement à la main ou bien à l"aide de la fiche réponse type fournie en annexe. Enfin, il est recommandé de lire l"intégralité du sujet avant de commencer afin d"effectuer les bons choix de structures de données dès le début. L"objectif de ce sujet est d"étudier divers algorithmes de multiplication de polynômes ainsi que leur complexité en fonction du nombre de termes des polynômes manipulés. Pour expérimenter ces algorithmes, nous considérerons ici des polynômes dont les coef- ficients sont desentiersmodulop= 12289. En d"autres termes, nous travaillerons dans l"anneau des polynômes(Z=pZ)[t]. Il est à noter que, commepest premier,Z=pZest un corps : tous ses éléments non nuls sont inversibles modulop. Dans la suite, nous appelleronspolynômedetaillenun polynôme de degré au plusn1:

A(t) =n1X

i=0a iti, où tous lesai2Z=pZ.

Un tel polynôme sera représenté par la donnée dun-uplet(ai)0i cette représentation soit unique, on veillera à ce que les coefficientsai(qui sont en fait des classes d"équivalence modulop) soient toujours représentés par l"unique entier~ai2 f0;:::;p1gde cette classe d"équivalence. Autrement dit,lescoefficientsdespolynômes doiventtoujoursêtreréduitsmodulop. Par exemple, le polynôme2t1, de taille2, sera représenté par le couple d"entiers(12288;2). Ce sujet se divise en quatre parties. Les trois dernières, traitant chacune un algorithme de multiplication différent, sont relativement indépendantes les unes des autres.

1 Préliminaires

1.1 Génération de polynômes aléatoires

Avant toute chose, considérons les trois suites d"entiers positifs(uk)k0,(vk)k0et(wk)k0 définies par u k=votreu0(à reporter sur votre fiche réponse) sik= 0,

17420uk1mod 32003sik >0,

v k=votreu0(le même) sik= 0,

17420vk1mod 32009sik >0,et

w k= (ukvk) modp, avecp= 12289. Question 1Donnez les valeurs(uk;vk;wk)pourkvalanta)5,b)50,c)500. Nous notons alorsPn;kle polynôme de taillenreprésenté par les coefficients(wkn+i)0i1.2 Fonction de signature Étant donnés deux entiersetr, nous définissons aussi une fonction de hachageHash;r qui, à toutn-uplet d"entiersA= (ai)0inômes, puisque tout polynôme de taillenpeut être représenté de manière unique par un

n-uplet d"entiers dansf0;:::;p1g. Attention toutefois à bien effectuer tout le calcul de Hash ;rmoduloret non pas modulop. Nous définissons enfin une fonction de signatureSigqui, elle aussi, peut être appliquée indifféremment auxn-uplets ou aux polynômes de taillen: Sig(A) = (Hash17;983(A);Hash23;991(A);Hash51;997(A)). Question 2Donnez la signatureSig(Pn;k)des polynômesPn;k(t)suivants : a)P10;0(t),b)P100;1(t),c)P1000;5(t). Remarque.Attention au dépassement de capacité des entiers machine lors du calcul des fonctions de hachageHash;r. Pensez à réduire les résultats intermédiaires modulor aussi souvent que nécessaire.

1.3 Opérations élémentaires

Étant donnés deux polynômesA(t)etB(t)(pas forcément de même taille) ainsi qu"un élémentc2Z=pZet un entier positifi, on définit les opérations classiques d" addition :A(t) +B(t); de soustraction :A(t)B(t); de multiplicationparunscalairecA(t); et de multiplicationpart i:A(t)ti. Question 3Calculez les polynômes suivants et donnez leur signature : a)P15;1(t) +P10;3(t),b)P100;1(t)P150;2(t),c)w42P1000;1(t),d)P4000;1(t)t17. Question à développer pendant l"oral :En supposant que les polynômesA(t)etB(t) soient de taillemetn, respectivement, donnez le coût exact de chacune de ces opérations, en matière d"additions et de multiplications dansZ=pZ. (Une soustraction ou un calcul d"opposé dansZ=pZsera compté comme une addition.)

Dans la suite du sujet, lorsqu"aucune ambiguïté n"est possible, on évitera d"écrire expli-

citement la variable(t)des polynômes afin de ne pas alourdir les notations. Ainsi, par exemple, on noteraA+Bla somme de deux polynômesA(t)etB(t).

2 Algorithme naïf

Question à développer pendant l"oral :Étant donnés deux polynômesA(t)etB(t) de taillemetn, respectivement, quelle est la taille de leur produit? Écrivez un algorithme naïf qui calcule ce produit. Quelle est sa complexité en temps et en mémoire? Combien d"additions et de multiplications dansZ=pZnécessite-t-il exactement? Question 4Calculez les produits de polynômes suivants et donnez leur signature : 2/7

3 Algorithme de Karatsuba

Dans cette partie, les polynômes que nous cherchons à multiplier sont tous deux de taillen= 2`, pour un entier`1. On noteA(t) =Pn1 i=0aitietB(t) =Pn1 i=0bitices polynômes. L"algorithme développé par Karatsuba en 1960 pour multiplier deux tels polynômes re- pose sur une approche de typediviserpourrégner. Pour cela, on commence par découper chaque polynôme en deux parties de taillen=2en écrivant

A(t) =A1(t)tn=2+A0(t), avecA0(t) =Pn=21

i=0aitietA1(t) =Pn=21 i=0an=2+iti, et

B(t) =B1(t)tn=2+B0(t), avecB0(t) =Pn=21

i=0bitietB1(t) =Pn=21 i=0bn=2+iti.

Le produitA(t)B(t)est alors donné par

A(t)B(t) =A1B1tn+ (A0B1+A1B0)tn=2+A0B0.

Tel qu"écrit ci-dessus, le produit de deux polynômes de taillenrequiert4produits de polynômes de taillen=2(les produitsA0B0,A0B1,A1B0etA1B1), ce qui n"apporte aucun avantage par rapport à l"algorithme naïf. Cependant, la méthode de Karatsuba permet d"effectuer le même calcul en seulement3 produits de taillen=2, au prix de quelques additions et soustractions supplémentaires, en remarquant que A

0B1+A1B0= (A0+A1)(B0+B1)A0B0A1B1.

Question à développer pendant l"oral :Quels sont ces3produits de taillen=2? En remarquant qu"il est possible d"appliquer récursivement la méthode de Karatsuba pour calculer ces produits, écrivez un algorithme calculant le produit de deux polynômes par cette méthode. Quel est sa complexité en temps et en mémoire? Indiquez le nombre exact d"additions et de multiplications dansZ=pZrequises pour multiplier deux polynômes de taillen= 2`. Question 5Calculez les produits de polynômes suivants et donnez leur signature : Question à développer pendant l"oral :Peut-on appliquer l"algorithme de Karatsuba à des polynômes dont la taillenn"est pas une puissance de2? Si oui, comment? Donnez une borne supérieure de la complexité de cet algorithme en fonction den. Et lorsque les deux polynômes n"ont pas la même taille?

4 Méthode par transformée de Fourier rapide

4.1 Multiplication par évaluation-interpolation

La multiplication par transformée de Fourier rapide appartient à la famille des algo- rithmes demultiplicationparévaluation-interpolation. Ces algorithmes reposent sur la

propriété qu"un polynômeA(t)de taillendéfini surZ=pZpeut être représenté de manière

3/7 unique par son évaluation ennpoints distincts(ti)0i4.2 Racines de l"unité Pour rappel, les polynômes que nous considérons sont à coefficients dansZ=pZ, avec p= 12289. Pour tout entier positifn, nous définissons alorsRn, l"ensemble desracinesn-ièmesde l"unité deZ=pZ, comme suit : R n=f!2Z=pZj!n= 1g. CommeRnest l"ensemble des racines dansZ=pZdu polynômetn1, il ne peut y avoir plus denracines de l"unité. De plus, sipne divise pasn, alors ce polynôme n"admet aucune racine multiple. Nous définissons aussiPn, l"ensemble desracinesn-ièmesprimitivesdel"unité : P n=f!2 Rnj!d6= 1pour toutddivisantn,d6=ng. Question à développer pendant l"oral :CalculezR3, l"ensemble des racines cubiques de l"unité dansZ=pZ. Lesquelles sont primitives? Question 6Pour chacun des couples(n;b)suivants, calculez la racine primitive!2 Pn telle que la différence(!b) modpsoit la plus petite possible. SiPnest vide, renvoyez a)(25;w10),b)(212;w100),c)(213;w1000). Question à développer pendant l"oral :Montrez que toute racinen-ième primitive de

l"unité!2 Pnpermet de générer l"ensemble des racinesn-ièmes de l"unitéRn, c"est-à-dire

que R n=f!0;!1;:::;!n1g. Si une telle racine primitive existe, quel est alors le cardinal deRn? 4/7

4.3 Transformée de Fourier discrète

Étant donné un polynômeA(t) =Pn1

i=0aitide taillenet!une racinen-ième primitive de l"unité dansZ=pZ, latransforméedeFourierdiscrète de ce polynôme en!, notée TFD !(A), est l"évaluation de celui-ci en lesnpoints distincts(!i)0i0` <12, nous définissons!2`=!212` 2

12. On pourra vérifier que!2`2 P2`pour tout

0`12. Question à développer pendant l"oral :Écrivez un algorithme qui, étant donné un polynômeA(t)de degrén= 2`, calcule de manière naïveTFD!2`(A), la transformée de Fourier discrète de ce polynôme en!2`. Quelle est sa complexité en temps et en mémoire? Question 7Pour chaque polynômePn;k(t)de taillen= 2`suivant, calculezTFD!2`(Pn;k), sa transformée de Fourier discrète en!2`, et donnez la signature de cette transformée : a)P24;0(t),b)P28;1(t),c)P212;2(t). Étant donné un polynômeA(t)de taillenet une racinen-ième primitive de l"unité!2 Pn, on peut considérer le polynôme de taillenassocié auxncoefficients de la transformée de Fourier discrète deA(t)en!, que l"on note^A(t):

A(t) =n1X

i=0A(!i)ti. En appliquant l"opération une seconde fois, mais en prenant cette fois-ci!1(l"inverse multiplicatif de!dansZ=pZ) comme racine primitive de l"unité, on obtient alors le polynôme de taillen ^A(t) =n1X i=0^

A(!i)ti,

dont les coefficients sont directement donnés parTFD!1(^A). Question à développer pendant l"oral :Vérifiez que^^A(t) =nA(t). Déduisez-en que les coefficients de l"interpolation d"un polynôme de taillenà partir de son évaluation en les racinesn-ièmes de l"unité(!i)0i1modp, l"inverse multiplicatif denmodulop.) Indication.Afin de prouver le résultat précédent, remarquez quePn1 i=0(!k)imodp= 0 pour tousn >0,k6= 0non divisible parnet!2 Pn. Question 8Pour chaque polynômePn;k(t)de taillen= 2`suivant, calculezTFD1 !2`(Pn;k), sa transformée de Fourier discrète inverse en!2`, et donnez la signature de cette trans- formée : a)P24;3(t),b)P28;4(t),c)P212;5(t). 5/7

4.4 Transformée de Fourier rapide

Si la transformée de Fourier discrète et son inverse présentées dans la section précédente

permettent d"évaluer et d"interpoler un polynôme auxnracinesn-ièmes de l"unité de

Z=pZ, la complexité de l"algorithme naïf pour calculer ces transformées est trop élevée

pour que cette approche présente un quelconque avantage par rapport à l"algorithme de multiplication classique ou à la méthode de Karatsuba. Cependant, l"algorithme detransforméedeFourierrapide, initialement mis au point par Gauss en 1805 puis redécouvert en 1965 par Cooley et Tukey, permet de calculer la transformée de Fourier discrète d"un polynôme bien plus efficacement.

Soitnun entier pair etA(t) =Pn1

i=0aitiun polynôme de taillen. On définit alors les deux polynômesA(0)(t)etA(1)(t)de taillen=2par A (0)(t) =n=21X i=0a

2itietA(1)(t) =n=21X

i=0a

2i+1ti,

de sorte à ce que l"on aitA(t) =A(0)(t2) +A(1)(t2)t. La transformée de Fourier discrèteTFD!(A), pour!2 Pn, revient donc à calculer les évaluationsA(!i) =A(0)(!2i) +A(1)(!2i)!ipour tout0i < n. Or, on peut remarquer que!2est une racine(n=2)-ième primitive de l"unité et que, pour tout0i < n=2,w2i=w2(i+n=2). Ainsi,A(0)(!2i) =A(0)(!2(i+n=2))est lei-ième coefficient deTFD!2(A(0)), la transformée de Fourier discrète deA(0), de taillen=2, en

22 Pn=2. Il en va de même pour les évaluationsA(1)(!2i).

Ainsi, si l"on note les(n=2)-uplets

^a(0) i

0i ^a(1) i

0i obtenus en calculant deux transformées de Fourier discrètes de taillen=2, on obtient lesquotesdbs_dbs47.pdfusesText_47