Exercice 19 - Représentation des polynômes

Nous souhaitons implémenter une bibliothèque de représentation des fonctiosn polynômes. La plupart des opérations sont relativement simples à rédiger. La plus délicate est la multiplication. Prenons un exemple, pour multiplier $P(x) = 1 + x + 2^2$ et $Q(x) = 1 - x + x^2$, il y a deux façons de procéder.

1. En multipliant "bêtement" : $P(x)Q(X) = (1 + x + 2^2)(1 - x + x^2) = 1(1 - x + x^2) + x[(1 - x + x^2)+ 2x(1... ... x - x^2 + 2x^3] = 1 - x + x^2 + x + x^2 - x^3 + 2x^4 = 1 + 2x^2 - x^3 + 2x^4.$
2. Une autre méthode consiste à passer par une interpolation. Le polynôme $PQ$ sera évidemment de degré $4$, donc en ayant $5$ points par lesquels passa la courbe de $PQ$, il est possible d'interpoler ses coefficients. Pour trouver ces points, il suffit d'évaluer $P$ et $Q$ en $5$ points, par exemple $\{1, 2, 3, 4, 5\}$, On obtient $2$ vecteurs
   
   $$\{(1, P(1)), (2, P(2)), (3, P(3)), (4, P(4)), (5, P(5))\}$$
   
   
   et
   
   $$\{(1, Q(1)), (2, Q(2)), (3, Q(3)), (4, Q(4)), (5, Q(5))\}$$
   
   
   Cela nous donne $5$ points par lesquels passe la courbe de $PQ$ :
   
   $$\{(1, P(1)Q(1)), (2, P(2)Q(2)), (3, P(3)Q(3)), (4, P(4)Q(4)), (5, P(5)Q(5))\}$$
   
   
   Il suffit ensuite d'effectuer une interpolation des coefficients $a, b, c, d$ et $e$ de la courbe de $PQ$, cela se fait en résolvant le système d'équations

   
   

   $$\{a1^4 + b1^3 + c1^2 + d1^1 + e = P(1)Q(1), a2^4 + b2^3 + c2^2 + d2^1 + e = P(2)Q(2), \ldots\}$$
   
   

Chacune de ces méthoes requiert $\mathcal {O}(n^2)$ opérations. Il est cependant possible d'affiner la deuxième en choisissant judicieusement les points servant à évaluer puis à interpoler. En prenant $W_n$ comme ensemble de points, on ramène les évaluations de ces points à des transformées de Fourier et l'interpolation à une transformation inverse de Fourier. Cela permet de multiplier des polynômes en $\mathcal{O}(n \log_2 n)$. Voyez [2] pour un exposé davantage détaillé. Ecrivez les fonctions du fichier polynomes.c correspondant au fichier polynomes.h ci-dessous. Vous prendrez soin de vous assurer que la multiplication à l'aide de la transformée de Fourier est plus rapide que la version pour boeufs.

#ifndef POLYNOME_H
#define POLYNOME_H

#include"linkedList.h"
#include"complexe.h"
#include"fourier.h"

/*
  Nous representerons un polynome avec une liste chainee contenant 
  les coefficients du polynome par ordre de degre croissant.
*/

/*
Retourne un polynome vide.
 */

linkedList* makePolynome();

/*
  Retourne une copie de l, copie aussi les coefficients.
*/
linkedList* copyPolynome(linkedList* l);

/*
  Detruit le polynome l et ses coefficients.
 */
void destroyPolynome(linkedList* l);

/*
  Affiche polynome le plus proprement possible.
*/
void printPolynome(linkedList* polynome);

/*
  Retourne le degre de l.
 */
int degreePolynome(linkedList *l);

/*
  Ajoute un monome de coefficient coeff a la fin du polynome, faisant 
  ainsi croutre son degre de 1.
*/
void appendCoeffPolynome(linkedList* polynome, double coeff);

/*
  Cree et retourne le polynome de degre n-1 dont les 
  coefficients sont passes dans le tableau d.
 */
linkedList* makeArrayPolynome(double* d, int n);

/*
  Retourne le polynome nul.
*/
linkedList* zeroPolynome();

/*
  Retourne le polynome unite.
*/
linkedList* unitPolynome();

/*
  Ajoute la constante d au polynome l.
*/
void addRealPolynome(linkedList* l, double d);

/*
  Multiplie le polynome l par le reel d.
*/
void multRealPolynome(linkedList* l, double d);

/*
  Multiplie le polynome l par X^n
*/
void multXNPolynome(linkedList* l, int n);

/*
  Multiplie le polynome l par coeff*X^exp 
*/
void multMonomePolynome(linkedList* l, double coeff, int exp);

/*
  Additione les deux polynomes a et b, retourne cette somme.
 */
linkedList* addPolynome(linkedList* a, linkedList* b);

/*
  Multiplie a et b avec la recurrence 
  (a_0 + a_1X + ... + a_nX^n)Q(X)
  = a_0 * Q(X) + X * (a_1 + a_2 X...+ a_n X^(n-1)) * Q(X)
*/
linkedList* slowMultPolynome(linkedList* a, linkedList* b);

/*
  Multiple a et b en passant par une transformee de fourier.
 */
linkedList* multPolynome(linkedList* a, linkedList* b);

/*
  Evalue le polynome l en x avec la methode de Horner.
 */
double evaluatePolynome(linkedList *l, double x);

#endif

polynomes.h