#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>
#include"polynomes.h"
/*--------------------------------------------------*/
/*
Retourne un polynome vide.
*/
linkedList* makePolynome()
{
return linkedListCreate();
}
/*--------------------------------------------------*/
/*
Alloue dynamiquement un emplacement pour une variable de type
double, y affecte d et retourne cette adresse.
*/
double* makeDouble(double d)
{
double* p = (double*)malloc(sizeof(double));
if (p == NULL)
exit(0);
*p = (double)d;
return p;
}
/*--------------------------------------------------*/
/*
Alloue dynamiquement un emplacement pour une variable de type
double, y affecte d et retourne cette adresse.
*/
void* makeDoubleWithVoid(void* v)
{
return makeDouble(*(double*)v);
}
/*--------------------------------------------------*/
/*
Desalloue une variable de type double.
*/
void destroyDouble(void* v)
{
free((double*)v);
}
/*--------------------------------------------------*/
/*
Retourne une copie de l, copie aussi les coefficients.
*/
linkedList* copyPolynome(linkedList* l)
{
return linkedListMap(l, makeDoubleWithVoid);
}
/*--------------------------------------------------*/
/*
Detruit le polynome l et ses coefficients.
*/
void destroyPolynome(linkedList* l)
{
linkedListDestroy(l, destroyDouble);
}
/*--------------------------------------------------*/
/*
Affiche le monome coeff * x^degre proprement, firstPrinted
est vrai si et seulement si ce monome est le premier affiche
dans le polynome.
*/
int printMonome(double coeff, int degre, int firstPrinted)
{
if (coeff != 0.0)
{
if (firstPrinted && coeff > 0.0)
printf(" + ");
if(coeff<0.0)
printf(" - ");
printf("%4.2lf", (coeff>0)?coeff:-coeff);
if(degre > 0)
printf("x");
if(degre > 1)
printf("^");
if(degre > 1)
printf("%d", degre);
return 1;
}
return 0;
}
/*--------------------------------------------------*/
/*
Affiche polynome le plus proprement possible.
*/
void printPolynome(linkedList* polynome)
{
int degre = 0, firstPrinted = 0;
void f(void* coeff)
{
if (printMonome(*(double*)coeff, degre, firstPrinted))
firstPrinted = 1;
degre++;
}
linkedListApply(polynome, f);
printf("\n");
}
/*--------------------------------------------------*/
/*
Supprime les O non significatifs à la fin du polynôme.
*/
void skipZerosPolynome(linkedList *l)
{
}
/*--------------------------------------------------*/
/*
Retourne le degre de l.
*/
int degreePolynome(linkedList *l)
{
int n;
skipZerosPolynome(l);
n = linkedListGetSize(l);
if(n != 1)
return n;
return (*(double*)linkedListGetFirst(l)->data != 0) - 1;
}
/*--------------------------------------------------*/
/*
Ajoute un monome de coefficient coeff a la fin du polynome, faisant
ainsi croutre son degre de 1.
*/
void appendCoeffPolynome(linkedList* polynome, double coeff)
{
double* p = malloc(sizeof(double));
if (p == NULL)
exit(0);
*p = coeff;
linkedListAppend(polynome, p);
}
/*--------------------------------------------------*/
/*
Cree et retourne le polynome de degre n-1 dont les
coefficients sont passes dans le tableau d.
*/
linkedList* makeArrayPolynome(double* d, int n)
{
linkedList* l = makePolynome();
int i;
for(i = 0 ; i < n ; i++)
appendCoeffPolynome(l, *(d + i));
return l;
}
/*--------------------------------------------------*/
/*
Retourne le polynome nul.
*/
linkedList* zeroPolynome()
{
linkedList* l = makePolynome();
appendCoeffPolynome(l, 0.0);
return l;
}
/*--------------------------------------------------*/
/*
Retourne le polynome unite.
*/
linkedList* unitPolynome()
{
linkedList* l = makePolynome();
appendCoeffPolynome(l, 1.0);
return l;
}
/*--------------------------------------------------*/
/*
Retourne le polynome
0 + X + 2X^2 + 3X^3 + ... + iX^i + ... + nX^n
*/
linkedList* simpleListPolynome(int n)
{
linkedList* l;
if (n == 0)
return zeroPolynome();
l = simpleListPolynome(n - 1);
appendCoeffPolynome(l, n);
return l;
}
/*--------------------------------------------------*/
/*
Ajoute la constante d au polynome l.
*/
void addRealPolynome(linkedList* l, double d)
{
link* lnk = linkedListGetFirst(l);
if (lnk != NULL)
*(double*)lnk->data += d;
else
appendCoeffPolynome(l, d);
}
/*--------------------------------------------------*/
/*
Multiplie le polynome l par le reel d.
*/
void multRealPolynome(linkedList* l, double d)
{
void multiplyDouble(void* v)
{
*(double*)v *= d;
}
linkedListApply(l, multiplyDouble);
}
/*--------------------------------------------------*/
/*
Multiplie le polynome l par X^n
*/
void multXNPolynome(linkedList* l, int n)
{
if (n > 0)
{
linkedListPush(l, makeDouble(0.0));
multXNPolynome(l, n - 1);
}
}
/*--------------------------------------------------*/
/*
Multiplie le polynome l par coeff*X^exp
*/
void multMonomePolynome(linkedList* l, double coeff, int exp)
{
multRealPolynome(l, coeff);
multXNPolynome(l, exp);
}
/*--------------------------------------------------*/
/*
Additionne deux à deux tous les maillons des deux listes la
et lb. Concatene le resultat a la liste result.
*/
void addMaillons(link* la, link* lb, linkedList* result)
{
if (la != NULL && lb != NULL)
{
appendCoeffPolynome(result, *(double*)la->data
+ *(double*)lb->data);
addMaillons(la->next, lb->next, result);
}
else
{
if (la != NULL)
{
appendCoeffPolynome(result, *(double*)la->data);
addMaillons(la->next, NULL, result);
}
if (lb != NULL)
{
appendCoeffPolynome(result, *(double*)lb->data);
addMaillons(NULL, lb->next, result);
}
}
}
/*--------------------------------------------------*/
/*
Additione les deux polynomes a et b, retourne cette somme.
*/
linkedList* addPolynome(linkedList* a, linkedList* b)
{
linkedList* result = makePolynome();
addMaillons(linkedListGetFirst(a),
linkedListGetFirst(b),
result);
return result;
}
/*--------------------------------------------------*/
/*
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)
{
linkedList* temp1 = NULL;
linkedList* res = zeroPolynome();
int n = 0;
void auxFunction(void* v)
{
linkedList* temp2 = copyPolynome(b);
multMonomePolynome(temp2, *(double*)v, n);
temp1 = addPolynome(res, temp2);
destroyPolynome(res);
destroyPolynome(temp2);
res = temp1;
n++;
}
linkedListApply(a, auxFunction);
return res;
}
/*--------------------------------------------------*/
/*
Fonction auxiliaire pour le sous-programme ci-dessous.
*/
void multMaillons(link* la, link* lb, linkedList* result)
{
pComplexe p;
if (la != NULL)
{
p = copyComplexe(
multComplexe(
*(pComplexe)la->data,
*(pComplexe)lb->data));
linkedListAppend(result, p);
multMaillons(la->next, lb->next, result);
}
}
/*--------------------------------------------------*/
/*
Multiplie entre eux tous les coefficients (complexes) des monomes de
meme degre, par exemple :
(1 + 2X + 4X^2) et (3 + X - 2X^2) donnent
(1 * 3) + (2 * 1)X + (4 * -2)X^2
a et b sont necessairement de meme degre.
*/
linkedList* multMonomesPolynome(linkedList* a, linkedList* b)
{
linkedList* l = makePolynome();
multMaillons(linkedListGetFirst(a),
linkedListGetFirst(b),
l);
return l;
}
/*--------------------------------------------------*/
/*
Convertit un double en pointeur sur complexe.
*/
void* complexOfDouble(void* v)
{
return copyComplexe(makeAffComplexe(*(double*)v, 0.0));
}
/*--------------------------------------------------*/
/*
Convertit un complexe en double, supprime
la partie imaginaire.
*/
void* doubleOfComplexe(void* v)
{
return makeDouble(reComplexe(*(pComplexe)v));
}
/*--------------------------------------------------*/
/*
Detruit un nombre complexe.
*/
void destroyComplexe(void* v)
{
free((pComplexe)v);
}
/*--------------------------------------------------*/
/*
Retourne la premier puisance de 2 superieure ou egal a x.
*/
int puiss2UpperThan(int x)
{
int k = 2;
while(k < x)
k *= 2;
return k;
}
/*--------------------------------------------------*/
/*
Ajoute des zeros non significatifs a la fin de l de sorte
que sa taille devienne k.
*/
void resizeList(linkedList* l, int k)
{
while(linkedListGetSize(l) < k)
linkedListAppend(l,
copyComplexe(makeAffComplexe(0.0, 0.0)));
}
/*--------------------------------------------------*/
/*
Modifie les tailles des deux listes de sorte
qu'on puisse leur appliquer une FFT
*/
void calibrateLists(linkedList* l1, linkedList* l2)
{
int k;
int length = linkedListGetSize(l1) +
linkedListGetSize(l2) - 1;
k = puiss2UpperThan(length);
resizeList(l1, k);
resizeList(l2, k);
}
/*--------------------------------------------------*/
/*
Multiple a et b en passant par une transformee de fourier.
*/
linkedList* multPolynome(linkedList* a, linkedList* b)
{
linkedList *ca, *cb, *ffta, *fftb, *prodab, *resComplexe, *res;
ca = linkedListMap(a, complexOfDouble);
cb = linkedListMap(a, complexOfDouble);
calibrateLists(ca, cb);
ffta = FFT(ca);
fftb = FFT(cb);
prodab = multMonomesPolynome(ffta, fftb);
resComplexe = inverseFFT(prodab);
res = linkedListMap(resComplexe, doubleOfComplexe);
linkedListDestroy(ca, destroyComplexe);
linkedListDestroy(cb, destroyComplexe);
linkedListDestroy(ffta, destroyComplexe);
linkedListDestroy(fftb, destroyComplexe);
linkedListDestroy(prodab, destroyComplexe);
linkedListDestroy(resComplexe, destroyComplexe);
return res;
}
/*--------------------------------------------------*/
/*
Evalue le polynome l en x avec la methode de Horner.
*/
double hornerLink(link* lnk, double x)
{
if (lnk == NULL)
return 0.0;
return *(double*)lnk->data +
x*hornerLink(lnk->next, x);
}
/*--------------------------------------------------*/
/*
Evalue le polynome l en x avec la methode de Horner.
*/
double evaluatePolynome(linkedList *l, double x)
{
return hornerLink(linkedListGetFirst(l), x);
}
/*--------------------------------------------------*/
int main()
{
linkedList *l = simpleListPolynome(10000);
//makeArrayPolynome(d, 5);
linkedList *m, *n, *p;
printf("multiplication\n");
m = slowMultPolynome(l, l);
printf("done\n");
//printPolynome(m);
printf("multiplication\n");
n = multPolynome(l, l);
printf("done\n");
//printPolynome(m);
multRealPolynome(n, -1);
p = addPolynome(m, n);
printf("test : %lf\n", evaluatePolynome(p, 1.0));
destroyPolynome(l);
destroyPolynome(m );
destroyPolynome(n );
return 0;
}