[PDF] Multiplication de polynômes





Previous PDF Next PDF



multiplication et division de polynômes

Multiplier deux polynômes implique l'utilisation des règles sur les puissances et la distributivité de la multiplication sur l'addition. Multiplication de deux 



Multiplication de polynômes

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



Multiplication rapide de polynômes

Indiquez le nombre exact d'additions et de multiplications dans Z/pZ requises pour multiplier deux polynômes de taille n = 2l. Question 5 Calculez les produits 



CC2 : Multiplication de polynômes

CC2 : Multiplication de polynômes. Durée de l'épreuve : 2h De plus on associe à ce polynôme une fonction polynomiale fP



Chapitre 1 - Polynômes `a coefficients dans un corps

La multiplication des polynômes est associative commutative



Multiplication de polynômes : Karatsuba FFT

Ces procédures seront faciles à appliquer à des polynômes grâce aux transformations liste-polynôme et polynôme- liste. Exercice 1 – [Karatsuba]. On désire 



CQP 099 - Mathématiques de base - Chapitre 2 Polynômes

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.



Chapitre 12 : Polynômes

7 févr. 2014 sait élever à une certaine puissance et multiplier par des éléments de K par exemple des matrices



Transformation de Fourier discrète 1 Multiplication de polynômes

multiplication de (grands) polynômes puis décrire l'algorithme FFT qui aibj nécessite n multiplications puis n additions



TD 3 : Multiplication de polynômes

TD 3 : Multiplication de polynômes. Exercice 1. est remplacé par la valeur du coefficient dominant du polynôme (« évaluation en ? »).

?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+

c

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+

a

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

a

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) =

q

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

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

p

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] 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