[PDF] Multiplication de polynômes - GRAAL PDF tp-caml-2006-04.pdf

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

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

?MP & MP?- Option Informatique

Ann´ee 2006-2007, Quatri`eme TP Caml

Multiplication de polynˆomes

Dans ce TP, nous allons ´etudier3fa¸cons diff´erentes de multiplier des polynˆomes `a coefficients

entiers. Ce sont3des4fa¸cons les plus utilis´ees dans les diff´erents logiciels. De plus, les mˆemes

techniques s"appliquent tr`es facilement aux multiplications de grands nombres entiers. Deux

des m´ethodes que nous allons voir utilisent la technique ditediviser pour r´egner, qui consiste

`a d´ecouper un gros probl`eme en deux (ou plus) sous-probl`emes qu"on subdivisera de nouveau. Cette technique est par exemple utilis´ee dans le tri fusion.

1 Diff´erentes fonctions auxilliaires

En Caml, aucun type "polynˆome" n"est pr´ed´efini; nousallons donc en d´efinir un, ainsi que des fonctions

de base (notamment pour acc´eder aux coefficients). ?Question 1D´efinissez un nouveau type Caml pour repr´esenter un polynˆome. Cela pourra ˆetre par exemple un vecteur d"entiers.Maintenant que l"on a ce type, il faut d´efinir des fonc- tions de base pour le rendre utilisable :?Question 2Ecrivez les fonctionsdegrequi renvoie le degr´e d"un polynˆome (ou plutˆot la taille du vecteur le repr´esentant),getcoefetsetcoefqui renvoie et d´efinit

le coefficient de degr´eid"un polynˆome, une fonctionnouveaupolynomequi cr´ee un polynˆome nul de tailledonn´ee, ainsi que la fonctionrandpolynomequi g´en`ere

un polynˆome de degr´e donn´e al´eatoirement (il n"y a pas besoin de faire attention `a avoir une distribution uni- forme, c"est uniquement pour tester). Pour la fonctionrandpolynome, on pourra utiliser lafonctionrandomint. degre : polynome->int = nouveaupolynome : int->polynome = getcoef : polynome->int->int = setcoef : polynome->int->int->unit = randpolynome : int->polynome =

Maintenant que nous avons ces fonctions de base,

nous pouvons d´efinir plusieurs op´erations de base : ?Question 3Ecrivez les fonctionsaddition(respec- tivementsoustraction) qui additionne (!) (respective- ment soustrait) deux polynˆomes. Ecrivez ´egalement une fonctiondecalepolynometelle quedecalepolynome : (P(X),n)?→P(X).Xn addition : polynome->polynome->polynome = soustraction : polynome->polynome->polynome = decalepolynome : polynome->int->polynome =2 Multiplication na¨ıve Dans cette partie, nous allons nous attarder sur l"al- gorithme na¨ıf de multiplication. Consid´erons les po- lynˆomesP(X) =a3X3+a2X2+a1X+a0etQ(X) = b

2X2+b1X+b0.

NotonsR(X) =P(X)Q(X) =c5X5+c4X4+c3X3+

2X2+c1X+c0.

On a c k=? i+j=k(aibj) .?Question 4Ecrivez une fonctionmultcoefqui prend en entr´ee deux polynˆomes et calcule lekemecoef-ficient du produit. multcoef : polynome->polynome->int->int = ?Question 5En utilisant la fonction pr´ec´edente, ´ecrivez une fonctionmultiplicationqui calcule le pro- duit de deux polynˆomes. multiplication : polynome->polynome->polynome =

3 Une m´ethode moins na¨ıve :

l"algorithme de Karatsuba L"objectif principal est de faire le moins de multipli- cations possibles, mˆeme si pour cela on doit rajouter un certain nombre d"additions. Consid´erons pour l"ins- tant deux polynˆomes de degr´e 1,P(X) =a1X+a0et

Q(X) =b1X+b0.

Leur produit est ´egal `aPQ(X) =a1b1X2+ (a0b1+

1b0)X+a0b0, qui n´ecessite 4 multiplications (a1b1,a0b1,

1b0,a0b0).

Comment r´eduire ce nombre?

Karatsuba a remarqu´e quea0b1+a1b0pouvait s"´ecrire sous la forme ((a0+a1)(b1+b0)-a1b1-a0b0qui ne n´ecessite qu"une seule multiplication (car les deux autres ont d´ej`a ´et´e calcul´ees). Nous allons donc d´ecouper les deux polynˆome de taille n= 2pen deux parties de degr´en/2-1 :P(X) = p

1(X)Xp/2+p0etQ(X) =q1(X)Xp/2+q0. Evi-

demment, les 3 produits interm´ediaires seront faits

r´ecursivement, en les red´ecoupant en 2.Cette m´ethode permet une complexit´e de l"ordre de

O(n1.59) multiplications pour des polynˆomes de degr´e n, au lieu deO(n2) multiplications pour la m´ethode na¨ıve (on gagne un facteur 100 pourn= 100000, par exemple). ?Question 6Malheureusement, tous les polynˆomes en libert´e n"ont pas un degr´e de la formen= 2p-1 (et donc une taille de la forme2p). Pour corriger ce re-

grettable d´efaut, programmez une fonction qui prend enargument deux polynˆomes et les "aggrandit" pour leur

donner une taille correcte (donc de la forme2p). arrondipolynome : polynome->polynome-> polynome?polynome = Maintenant, il faut pouvoir faire l"op´eration inverse, afin d"avoir des r´esultats plus lisibles.?Question 7Ecrivez une fonctionsimplifiepolynome qui supprime les coefficients nuls en tˆete d"un polynˆome. simplifiepolynome : polynome->polynome =

?Question 8Pour utiliser la m´ethode de Karatsuba, ilfaut pouvoir d´ecouper les deux polynˆomes `a multiplier en2polynˆomes de tailles ´egales. Ecrivez donc une fonctiondecoupepolynomequi prend en argument2polynˆomes

quelconques, leur donne une taille correcte (de la forme 2 p) et les coupe en deux sous-polynˆomes de mˆeme taille. decoupepolynome : polynome->polynome-> polynome?polynome?polynome?polynome =

?Question 9Ecrivez une premi`ere versionkaratsubasimplequi d´ecoupe les deux arguments en2polynˆomes de mˆeme taille, calcule les produits in-term´ediaires avec la fonctionmultiplicationna¨ıveet reconstruit la r´eponse avec les fonctionsaddition,decalepolynomeetsoustraction.

karatsubasimple : polynome->polynome->polynome = ?Question 10Ecrivez une fonction r´ecursivekaratsubaqui ne plus appel `amultiplicationpour les produits interm´ediaires (sauf quand les produits `a cal- culer ont un degr´e inf´erieur `a1).

karatsuba : polynome->polynome->polynome =En "vrai", les multiplications des petits polynˆomes de

degr´e 1 ne sont pas faites avec la m´ethode na¨ıve. La m´ethode utilis´ee consiste `a les ´evaluer en 3 points (par exemple 0, 1, et 2), calculer les 3 produitsP(0)Q(0), P(1)Q(1) etP(2)Q(2) et interpoler le r´esultat.

4 Autre m´ethode : Toom-3

Nous allons ´etudier un cas particulier (Toom-3) d"une g´en´eralisation de la m´ethode de Karatsuba (Toom-k). Au lieu de d´ecouperPetQen 2 sous-polynˆomes, l"id´ee est de les couper en 3 morceaux de mˆeme taille, toujours dans l"espoire de r´eduire le nombre de multiplications.

Supposons quePetQsoient tous les deux de taille

3n(donc de degr´e 3n-1). On peut alors ´ecrire

P(X) =p2X2n+p1(X)Xn+p0(X) etQ(X) =

2X2n+q1(X)Xn+q0(X). Le produitPQ(X) vaut ainsi

PQ(X) =p2q2X4n+(p2q1+p1q2)X3n+(p2q0+p1q1+

0q2)X2n+ (p1q0+p0q1)Xn+p0q0.

On ´ecrit alors (p2q1+p1q2) = (p1+p2)(q2+q1)-p1q1- q

2p2, (p0q1+p1q0) = (p1+p0)(q0+q1)-p1q1-q0p0, et

(p2q0+p0q2) = (p0+p2)(q2+q0)-p0q0-q2p2. Cette m´ethode se fait en 6 multiplications (au lieu de 9) mais une m´ethode avec 5 multiplications est cens´ee exister. Cette m´ethode permet une complexit´e de l"ordre de O(n1.47) multiplications, on gagne alors un facteur 450

pourn= 100000 par rapport `a la multiplication na¨ıve.?Question 11Ecrivez une fonctionarronditoom3qui

prend en argument2polynˆomes et renvoie deux po-lynˆomes ´egaux, mais dont la taille est un multiple de3.

arronditoom3 : polynome->polynome->polynome?polynome = ?Question 12Ecrivez une fonctiondecoupetoom3 qui prend en argument2polynˆomes et qui renvoie6 sous-polynˆomes de mˆeme taillen/3. decoupetoom3 : polynome->polynome-> polynome?polynome?polynome?polynome?polynome?polynome =

?Question 13Ecrivez une fonctiontoom3qui cal-cule le produit de2polynˆomes en utilisant les fonc-tions pr´ec´edentes. On pourra utiliser la fonctionmultiplicationpour les polynˆomes de degr´e inf´erieur `a2.

toom3 : polynome->polynome->polynome = La derni`ere m´ethode classique de multiplication de po- lynˆomes est bas´ee sur la Transform´ee de Fourier Ra- pide (FFT), qui a une complexit´e enO(nlogn)(gain sup´erieur `a8000pourn= 100000). 2 ?MP & MP?- Option Informatique

Ann´ee 2006-2007, Quatri`eme TP Caml

Multiplication de polynˆomes

Un corrig´e

?Question 1type polynome = coef of int vect;;

?Question 2let degre = fun (coef a)->(vectlength a)-1;;let nouveaupolynome = fun n->(coef (makevect (n+1) 0));;

let getcoef = fun (coef a) i->let n = (vectlength a-1) inif (i>n) then 0else a.(n-i);; let setcoef = fun (coef a) i v->let n = (vectlength a-1) inif(i<= n) then a.(n-i)<-v;; let randpolynome = fun degre->let resultat = nouveaupolynome degre in for i = 0 to degre do ( setcoef resultat i ((randomint 1000)-500 );) done; resultat let a = randpolynome 10;; let b = randpolynome 15;; ?Question 3let addition = fun (coef p) (coef q)->let n = degre (coef p) and m = degre (coef q) in let resultat = nouveaupolynome (max n m) in for i = 0 to (max n m) do setcoef resultat i ((getcoef (coef p) i) + (getcoef (coef q) i)) done; resultat addition a b;; let soustraction = fun (coef p) (coef q)->let n = degre (coef p) and m = degre (coef q) in let resultat = nouveaupolynome (max n m) in for i = 0 to (max n m) do setcoef resultat i ((getcoef (coef p) i)-(getcoef (coef q) i)) done; resultat soustraction a b;;

let decalepolynome = fun (coef p) k->let n = degre (coef p) inlet resultat = nouveaupolynome (n + k) in

for i = 0 to n do (setcoef resultat (i+k) (getcoef (coef p) i);) done; resultat

?Question 4let multcoef = fun (coef p) (coef q) i->let n = degre (coef p) and m = degre (coef q) and temp = ref 0 in

temp := 0;

for j = (max (i-n) 0) to (min m i) do (temp := !temp + (getcoef (coef p) (i-j))?(getcoef (coef q) j);

done; !temp

?Question 5let multiplication = fun (coef p) (coef q)->let n = degre (coef p) and m = degre (coef q) in

let resultat = nouveaupolynome (n + m) in for i = 0 to (n + m) do ( setcoef resultat i (multcoef (coef p) (coef q) i); done; resultat multiplication a b;;

?Question 6let arrondipolynome = fun (coef p) (coef q)->let n = degre (coef p) and m = degre (coef q) in

let temp0 = ((max n m) + 1) and temp1 = ref 0 and temp2 = ref 0. in temp1 := temp0; temp2 := log (floatofint !temp1); temp2 := (!temp2) /. (log 2.);

(?oui, je sais, ce n"est pas joli, mais je prefere bien separer les etapes?)temp1 := intoffloat !temp2;

temp1 := intoffloat (2.??. (floatofint !temp1));

if ( !temp1<>temp0) then temp1 := !temp1?2;(?il n"y a pas de partie enti`ere sup´erieure en Caml :(?)temp1 := (!temp1)-1;let pprime = nouveaupolynome (!temp1) in

let qprime = nouveaupolynome (!temp1) in for i = 0 to n do (setcoef pprime i (getcoef (coef p) i);) done; for i = 0 to m do (setcoef qprime i (getcoef (coef q) i);) done; (pprime, qprime) arrondipolynome (randpolynome 3) (randpolynome 4);; ?Question 7 let simplifiepolynome = fun (coef p)->let n = degre (coef p) in let i = ref n in

while((!i>= 0)&&(getcoef (coef p) !i = 0)) do ( i := !i-1 ; ) done;let resultat = nouveaupolynome !i in

for j = 0 to (!i) do (setcoef resultat j (getcoef (coef p) j);) done; resultat

?Question 8let decoupepolynome = fun (coef p) (coef q)->let (pprime, qprime) = arrondipolynome (coef p) (coef q) in

let n = (((degre pprime) + 1)/2-1) inlet p1 = nouveaupolynome n and p0 = nouveaupolynome n in let q1 = nouveaupolynome n and q0 = nouveaupolynome n in for i = 0 to n do ( setcoef p0 i (getcoef pprime i); setcoef p1 i (getcoef pprime (i+n+1)); setcoef q0 i (getcoef qprime i); setcoef q1 i (getcoef qprime (i+n+1)); done; (p0, p1, q0, q1) ?Question 9let karatsubasimple = fun p q->let (p0, p1, q0, q1) = decoupepolynome p q in

(?p = p0 + Xˆ(2n)?p1; q = q0 + Xˆ(2n)?q1?)let p1q1 = multiplication p1 q1 and p0q0 = multiplication p0 q0 in

let n = (degre p0) + 1 in let temp1 = addition p1q1 p0q0 in let p1p0 = addition p1 p0 in let q1q0 = addition q1 q0 in let temp2 = multiplication p1p0 q1q0 in let centre0 = soustraction temp2 temp1 in let centre1 = decalepolynome centre0 (n) in simplifiepolynome (addition (decalepolynome p1q1 (2?n)) (addition centre1 p0q0));; ?Question 10let rec karatsuba = fun p q->let (p0, p1, q0, q1) = decoupepolynome p q in (?p = p0 + Xˆ(2n)?p1; q = q0 + Xˆ(2n)?q1?)let n = (degre p0) + 1 in if n<= 1 then (multiplication p q; else ( let p1q1 = karatsuba p1 q1 and p0q0 = karatsuba p0 q0 in let temp1 = addition p1q1 p0q0 in let p1p0 = addition p1 p0 in let q1q0 = addition q1 q0 in let temp2 = multiplication p1p0 q1q0 in let centre0 = soustraction temp2 temp1 in let centre1 = decalepolynome centre0 (n) in simplifiepolynome (addition (decalepolynome p1q1 (2?n))(addition centre1 p0q0)); multiplication a b;; karatsubasimple a b;; karatsuba a b;;

?Question 11let arronditoom3 = fun (coef p) (coef q)->let n = degre (coef p) and m = degre (coef q) in

let temp0 = ((max n m) + 1) in let temp1 = ref (temp0/3) in if (3?(!temp1)?Question 12let decoupetoom3 = fun (coef p) (coef q)->let (pprime, qprime) = arronditoom3 (coef p) (coef q) in

let n = (((degre pprime) + 1)/3-1) inlet p1 = nouveaupolynome n and p0 = nouveaupolynome n in let q1 = nouveaupolynome n and q0 = nouveaupolynome n in let p2 = nouveaupolynome n and q2 = nouveaupolynome n inquotesdbs_dbs47.pdfusesText_47

[PDF] [PDF] Multiplication de polynômes - GRAAL

Ann´ee 2006-2007, Quatri`eme TP Caml

Multiplication de polynˆomes

1 Diff´erentes fonctions auxilliaires

Maintenant que nous avons ces fonctions de base,

2X2+b1X+b0.

NotonsR(X) =P(X)Q(X) =c5X5+c4X4+c3X3+

2X2+c1X+c0.

3 Une m´ethode moins na¨ıve :

Q(X) =b1X+b0.

Leur produit est ´egal `aPQ(X) =a1b1X2+ (a0b1+

1b0)X+a0b0, qui n´ecessite 4 multiplications (a1b1,a0b1,

1b0,a0b0).

Comment r´eduire ce nombre?

1(X)Xp/2+p0etQ(X) =q1(X)Xp/2+q0. Evi-

4 Autre m´ethode : Toom-3

Supposons quePetQsoient tous les deux de taille

3n(donc de degr´e 3n-1). On peut alors ´ecrire

P(X) =p2X2n+p1(X)Xn+p0(X) etQ(X) =

2X2n+q1(X)Xn+q0(X). Le produitPQ(X) vaut ainsi

PQ(X) =p2q2X4n+(p2q1+p1q2)X3n+(p2q0+p1q1+

0q2)X2n+ (p1q0+p0q1)Xn+p0q0.

2p2, (p0q1+p1q0) = (p1+p0)(q0+q1)-p1q1-q0p0, et

Ann´ee 2006-2007, Quatri`eme TP Caml

Multiplication de polynˆomes

Un corrig´e