[maths] Polynômes à un nombre quelconque de variables

**Zavonen** · 11/06/2008, 02h59

L'idée de développer le présent module vient d'une discussion assez ancienne avec Pseudocode concernant les polynômes à un nombre quelconque de variable.
Il me fallait une implémentation qui mette en relief les isomorphismes K[X,Y] <-->K[X][Y] et plus généralement K[X1,X2,....Xn] <--> K[X1,..Xi][Xi+1,...,Xn]
Je vois qu'il y a aujourd'hui une demande, c'est pourquoi je poste
Voici donc le module développé en C++ au moyen des templates pour avoir des polynômes à coefficients dans un corps quelconque.
Comme application on calcule les polynômes symétriques élémentaires:
Voici les headers:

exposant_multiple.h

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#ifndef EXPOSANT_MULTIPLE_H
#define EXPOSANT_MULTIPLE_H
#include <string>
#include <stdlib.h>
 
using namespace std;
 
class exposant_multiple
{
private:
    // comme son nom l'indique
    unsigned int nombre_de_variables;
    // le tableau des exposants pour X1,X2,....,Xn
    unsigned int * exposants;
public:
    // constructeurs
    exposant_multiple();
    exposant_multiple(int);
    // de copie
    exposant_multiple(exposant_multiple &other);
    //destructeur
    virtual ~exposant_multiple();
    //affectation
    exposant_multiple& operator= (exposant_multiple&);
    // test égalité
    bool operator==(exposant_multiple&);
    // accès aux exposants individuels
    unsigned int& operator[] (unsigned int i);
    // règle d'addition
    exposant_multiple& operator+ (exposant_multiple &other);
    // soustraction
    exposant_multiple& soustract(unsigned int var, unsigned int puiss);
    // représentation comme chaîne pour affichage
    friend ostream& operator<< (ostream& os,exposant_multiple e);
    // degré
    int degre();
protected:
 
};
 
#endif // EXPOSANT_MULTIPLE_H

monome.h

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#ifndef MONOME_H
#define MONOME_H
#include "exposant_multiple.h"
 
// juste pour la déclaration d'amitié
template <typename T>
class polynome;
 
template <typename T>
class monome
{
private:
    T coefficient;
    exposant_multiple exposant;
public:
    // constructeurs
    monome();
    monome(T,exposant_multiple&);
    virtual ~monome();
    // produit d'un monome par un autre
    monome& operator* (monome& other);
    // affectation
    monome& operator= (monome& other);
    // test de nullité du coeff
    bool est_nul();
    //pour les sorties sur écran ou sur fichier
    template <typename X>
    friend ostream& operator<< (ostream& os, monome<X>& M);
    // les méthodes des polynomes peuvent manipuler les données des monomes
    friend class polynome<T>;
    // le degre
    int degre()
    {
        return exposant.degre();
    }
    // test pour savoir si la variable de rang var intervient avec la puissance puiss
    bool contient (unsigned int var, unsigned int puiss);
    // quotient par une puissance d'une variable
    monome& quotient (unsigned int var, unsigned int puiss);
};
 
template <typename T>
monome<T>::monome()
{
    coefficient=0;
}
 
template <typename T>
monome<T>::monome(T c,exposant_multiple& m)
{
    coefficient=c;
    exposant=m;
}
 
template <typename T>
monome<T>::~monome()
{
}
 
// sortie sur écran ou sur fichier texte
template <typename X>
ostream& operator<< (ostream& os, monome<X>& M)
{
    if (M.coefficient==1)
    {
        os<<"+";
        os<<M.exposant;
    }
    else if (M.coefficient==-1)
    {
        os<<"-";
        os<<M.exposant;
    }
 
    else if (M.coefficient>=0)
    {
        os<<"+";
        os<<M.coefficient;
        os<<M.exposant;
    }
    else
    {
        os<<M.coefficient;
        os<<M.exposant;
    }
    return os;
}
 
 
template <typename T>
monome<T>& monome<T>::operator* (monome<T>& other)
{
    T coef= coefficient*other.coefficient;
    exposant_multiple* expo =new exposant_multiple((*this).exposant+other.exposant);
    monome<T>* result=new monome(coef,*expo);
    return *result;
}
 
template <typename T>
monome<T>& monome<T>::operator= (monome<T>& other)
{
    coefficient=other.coefficient;
    exposant=other.exposant;
    return *this;
}
template <typename T>
bool monome<T>::est_nul()
{
    return coefficient==0;
}
template <typename T>
monome<T>& monome<T>::quotient (unsigned int var, unsigned int puiss)
{
    monome<T> * resultat = new monome<;T>(*this);
    resultat->exposant=this->exposant.soustract(var,puiss);
    return *resultat;
}
 
template <typename T>
bool monome<T>::contient (unsigned int var, unsigned int puiss)
{
    return this->exposant[var]==puiss;
}
 
#endif // MONOME_H

polynome.h

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
#ifndef POLYNOME_H
#define POLYNOME_H
#include "monome.h"
 
template <typename T>
class polynome
{
private:
    unsigned int nombre_de_termes;
    monome<T> * termes;
public:
    //constructeurs
    // par défaut
    polynome();
    // à un paramètre
    polynome(int);
    //de recopie
    polynome(polynome<T>&);
    //destructeur
    virtual ~polynome();
    monome<T>& operator[](unsigned int);
    // affectation
    polynome<T>& operator= (polynome<T>&);
    // teste si aucun monome nul dans la somme
    bool est_propre();
    // enlève le monome de rang i
    void supprime(unsigned int );
    // supprime le premier monome nul
    void enleve_premier_nul();
    // supprime tous les monomes nuls
    void nettoie();
    // regroupe suivant les exposants identiques
    void regroupe();
    //produit d'un polynome par un monome
    polynome<T>& operator* (monome<T>&);
    //ajout d'un monome à un polynome
    polynome<T>& operator+ (monome<T>&);
    // somme de deux polynomes
    polynome<T>& operator+ (polynome<T>&);
    // produit d'un polynome par un autre
    polynome<T>& operator* (polynome<T>&);
    //puissance entière d'un polynome n>=1
    polynome<T>& operator^ (unsigned int n);
    //produit par un scalaire
    polynome<T>& operator* (T lambda);
    //opposé d'un polynome
    polynome<T>&amp; operator- ()
    {
        return (*this)*(-1);
    };
    // différence
    polynome<T>& operator- (polynome<T>& other)
    {
        return (*this)+other*(-1);
    };
    // le degre
    int degre();
    // facteur d'une inconnue à une certaine puissance
    polynome<T>& facteur(unsigned int var, unsigned int puiss);
    //sortie sur écran ou fichier
    template <typename X>
    friend ostream& operator<< (ostream& os, polynome<X>& );
};
 
template <typename X>
ostream& operator<< (ostream& os,polynome<X>& p)
{
    for (unsigned int i=0; i< p.nombre_de_termes;i++)
        os<<p[i];
    return os;
}
 
template <typename T>
polynome<T>::polynome()
{
    nombre_de_termes=0;
    termes= NULL;
}
 
template <typename T>
polynome<T>::polynome(int n)
{
    nombre_de_termes=n;
    termes= new monome<T>[n];
}
 
template <typename T>
polynome<T>::polynome(polynome<T>& other)
{
    nombre_de_termes=other.nombre_de_termes;
    termes=new monome<T>[nombre_de_termes];
    for (unsigned int i=0; i<nombre_de_termes;i++)
        termes[i]=other.termes[i];
}
 
 
template <typename T>
polynome<T>::~polynome()
{
    delete[] termes;
}
 
template <typename T>
monome<T>& polynome<T>::operator[](unsigned int i)
{
    return termes[i];
}
 
 
template <typename T>
void polynome<T>::supprime(unsigned int i)
{
    if (nombre_de_termes<=1)
        return;
    monome<T> * nouveaux_termes = new monome<T>[nombre_de_termes -1];
    for (unsigned int j=0,k=0; j<nombre_de_termes;j++)
        if (j!=i)
        {
            nouveaux_termes[k]=termes[j];
            k++;
        }
    delete[] termes;
    termes=nouveaux_termes;
    nombre_de_termes--;
}
 
template <typename T>
polynome<T>& polynome<T>::operator= (polynome<T>& other)
{
    nombre_de_termes=other.nombre_de_termes;
    termes=other.termes;
    return *this;
}
 
template <typename T>
bool polynome<T>::est_propre()
{
    if (nombre_de_termes<=1)
        return true;
    for (unsigned int i=0; i<nombre_de_termes;i++)
        if (termes[i].coefficient==0)
            return false;
    return true;
}
 
template <typename T>
void polynome<T>::enleve_premier_nul()
{
    for (unsigned int i=0; i<nombre_de_termes;i++)
        if (termes[i].coefficient==0)
        {
            supprime(i);
            return;
        }
}
 
template <typename T>
void polynome<T>::nettoie()
{
    while (!est_propre())
        enleve_premier_nul();
}
 
template <typename T>
void polynome<T>::regroupe()
{
    for (unsigned int i=0; i<nombre_de_termes;i++)
        for (unsigned int j=i+1;j<nombre_de_termes;j++)
            if (termes[i].exposant==termes[j].exposant)
            {
                termes[i].coefficient=termes[i].coefficient+termes[j].coefficient;
                termes[j].coefficient=0;
            }
    nettoie();
}
 
template <typename T>
polynome<T>& polynome<T>::operator* (monome<T>& M)
{
    polynome<T> * resultat=new polynome<T>(nombre_de_termes);
 
    for (unsigned int i=0; i<nombre_de_termes;i++)
        resultat->termes[i]=termes[i]*M;
    return *resultat;
}
 
template <typename T>
polynome<T>& polynome<T>::operator+ (polynome<T>& other)
{
    polynome<T> * resultat=new polynome<T>(nombre_de_termes+other.nombre_de_termes);
    unsigned int k=0;
    for (unsigned int i=0; i<nombre_de_termes;i++)
        resultat->termes[k++]=termes[i];
    for (unsigned int j=0; j<other.nombre_de_termes;j++)
        resultat->termes[k++]=other.termes[j];
    resultat->regroupe();
    return *resultat;
}
 
template <typename T>
polynome<T>& polynome<T>::operator* (polynome<T>& other)
{
    polynome<T> * resultat=new polynome<T>(0);
    for (unsigned int j=0; j<other.nombre_de_termes;j++)
    {
        polynome<T> * partiel=new polynome<T>;
        *partiel=(*this)*other.termes[j];
        *resultat=*resultat+*partiel;
        delete partiel;
    }
    resultat->regroupe();
    return *resultat;
}
 
template <typename T>
polynome<T>& polynome<T>::operator^ (unsigned int n)
{
    polynome<T>  *resultat=new polynome<T>(*this);
    for (unsigned int j=1; j<n;j++)
    {
        *resultat=*resultat*(*this);
    }
    resultat->regroupe();
    return *resultat;
}
 
template <typename T>
polynome<T>& polynome<T>::operator* (T lambda)
{
    polynome<T>  *resultat=new polynome<T>(*this);
    for (unsigned int j=0; j<nombre_de_termes;j++)
        (*resultat)[j].coefficient=(*this)[j].coefficient*lambda;
    return *resultat;
}
 
template <typename T>
int polynome<T>::degre()
{
    int d=0;
    for (unsigned int i=0;i<nombre_de_termes;i++)
        if (termes[i].degre()>d)
            d=termes[i].degre();
    return d;
}
template <typename T>
polynome<T>& polynome<T>::operator+ (monome<T>& M)
{
    polynome<T> * result = new polynome<T>;
    result->nombre_de_termes=this->nombre_de_termes+1;
    result->termes= new monome<T> [result->nombre_de_termes];
    for (unsigned int i=0; i<nombre_de_termes;i++)
        (*result)[i]=(*this)[i];
    (*result)[nombre_de_termes]=M;
    return *result;
}
template <typename T>
polynome<T>& polynome<T>::facteur(unsigned int var, unsigned int puiss)
{
    polynome<T> * result = new polynome;
    for (unsigned int i=0; i<nombre_de_termes;i++)
    {
        if ((*this)[i].contient(var,puiss))
            *result = *result + (*this)[i].quotient(var,puiss);
    }
    return *result;
}
#endif // POLYNOME_H

Voici les fichiers d'implémentation:
exposant_multiple.cpp

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include "exposant_multiple.h"
 
unsigned int max(unsigned int i, unsigned int j)
{
    return (i>j)?i:j;
}
 
exposant_multiple::exposant_multiple()
{
    //ctor
    nombre_de_variables=0;
    exposants=NULL;
}
 
 
exposant_multiple& exposant_multiple::operator= (exposant_multiple& other)
{nombre_de_variables=other.nombre_de_variables;
 unsigned int * nouveaux_exposants=new unsigned int [nombre_de_variables];
 for (unsigned int i=0;i<nombre_de_variables;i++)
 nouveaux_exposants[i]=other.exposants[i];
 delete [] exposants;
 exposants=nouveaux_exposants;
 return *this;
}
exposant_multiple::exposant_multiple(int n)
{
    //ctor
    nombre_de_variables= n;
    if (!n)
        exposants=NULL;
    else
        exposants= new unsigned int [n];
}
 
exposant_multiple::exposant_multiple(exposant_multiple& other)
{
    //ctor
    nombre_de_variables= other.nombre_de_variables;
    if (!nombre_de_variables)
        exposants=NULL;
    else
        exposants = new unsigned int [nombre_de_variables];
    for (unsigned int i=1;i<=nombre_de_variables;i++)
        (*this)[i]=other[i];
}
 
exposant_multiple::~exposant_multiple()
{
    if(exposants)
    delete[] exposants;
}
 
 
bool exposant_multiple::operator==(exposant_multiple& other)
{
    if (nombre_de_variables!=other.nombre_de_variables)
        return false;
    else
        for (unsigned int i=1; i<=nombre_de_variables;i++)
            if ((*this)[i]!=other[i]) return false;
    return true;
}
 
unsigned int& exposant_multiple::operator[] (unsigned int i)
{
    static unsigned int zero=0;
    if (i<=nombre_de_variables)
        return exposants[i-1];
    else
        return zero;
}
 
exposant_multiple& exposant_multiple::operator+ (exposant_multiple &other)
{
    unsigned int n=max(nombre_de_variables,other.nombre_de_variables);
    exposant_multiple * result  =new exposant_multiple(n);
    if (n&gt;0)
    {
        for (unsigned int i=1;i<=n;i++)
            (*result)[i]=(*this)[i]+other[i];
    }
    return *result;
}
 
ostream& operator<< (ostream& os, exposant_multiple e)
{
    char in[3];
    char exp[3];
    if (!e.nombre_de_variables)
        os<<string("");
    else
    {
        for (unsigned i=1;i<=e.nombre_de_variables;i++)
        {
            if (e[i])
            {
                os<<string("X");
                sprintf(in,"%d",i);
                os<<string(in);
                if (e[i]>1)
                {
                    sprintf(exp,"%d",e[i]);
                    os<<string("^")<<string(exp);
                }
            }
        }
    }
    return os;
}
 
int exposant_multiple::degre()
{ if (!exposants) return 0;
 int d=0;
 for(unsigned int i=0;i<nombre_de_variables;i++)
 d+=exposants[i];
 return d;
}
 
exposant_multiple& exposant_multiple::soustract(unsigned int var, unsigned int puiss)
{if (var>nombre_de_variables)
 return *this;
 else if (puiss>(*this)[var])
 return *this;
 else
 {exposant_multiple * resultat=new exposant_multiple(*this);
 (*resultat)[var]-=puiss;
 return *resultat;
 }
}

main.cpp

Code C++ :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/****************Polynomes de degré quelconque ***************/
/************à un nombre quelconque de variables***************/
/*************à coefficients dans n'importe quel type prédéfini *************/
/**************par Zavonen*************************************/
/*****************décembre 2007*******************************/
 
#include <iostream>
#include "polynome.h"
using namespace std;
 
// Un exemple d'application: Calcul des polynomes symétriques élémentaires
// de tous ordres et de tous degrés
 
#define ordre 14
 
// utilitaires pour les problèmes de signe des polynômes symétriques élémentaires
bool Pair(unsigned int i)
{
    return !(i%2);
}
 
bool Impair(unsigned int i)
{
    return i%2;
}
// pour contenir {1,0,0,0},{0,1,0,..}, ....{0,0,...1}
exposant_multiple e[ordre];
// Pour contenir les monomes X1,X2, ...
monome<int> X[ordre];
//Pour les polynomes à un seul terme X1, X2,....
polynome<int> P[ordre];
// Pour les binomes différences X4-X1, X4-X2,.....
polynome <int> D[ordre-1];
// Pour le produit des différences précédentes
polynome <int> Produit;
// Pour les polynomes symétriques élémentaires
polynome <int> PSE[ordre-1];
 
// Fonction qui initialise toutes les variables globales
void init()
{
    for (unsigned int i=0;i<ordre;i++)
    {
        exposant_multiple * pem= new exposant_multiple (ordre);
        for (unsigned int j=1;j<=ordre;j++)
            (*pem)[j]=(i==j-1)?1:0;
        e[i]=*pem;
        delete pem;
    }
    for (unsigned int i=0;i<ordre;i++)
    {
        monome<int> * pm = new monome<int>(1,e[i]);
        X[i]=*pm;
        delete pm;
    }
    for (unsigned int i=0;i<ordre;i++)
    {
        polynome<int> * ppol=new polynome<int>(1);
        (*ppol)[0]=X[i];
        P[i]=*ppol;
    }
    for (unsigned int i=0;i<ordre-1;i++)
    {
        D[i]=P[ordre-1]-P[i];
    }
    Produit=D[0];
    for (unsigned int i=1;i<ordre-1;i++)
        Produit=Produit*D[i];
    for (unsigned int i=0;i<ordre-1;i++)
    {
        PSE[i]=Produit.facteur(ordre,i);
        if ((Pair(ordre))&&(Pair(i)))
            PSE[i]=PSE[i]*(-1);
        if ((Impair(ordre))&&(Impair(i)))
            PSE[i]=PSE[i]*(-1);
    }
}
 
// Voir les polynomes symétriques
void show()
{
    for (unsigned int i=0;i<ordre-1;i++)
        cout<<PSE[i]<<endl;
}
 
int main()
{
    init();
    show();
    return 0;
}

**SpiceGuid** · 25/08/2008, 15h23

Tout ça me rappèle que j'aimerais bien, un jour, généraliser mon module d'arithmétique entière.

Malheureusement ma culture mathématique n'est pas assez large pour décider de la bonne interface.
D'autre part la notion de foncteur (mapping d'une structure vers une autre) en OCaml semble vaguement correspondre à celle de la théorie des catégories mais je ne vois nulle documentation où cette relation serait explicitée.

C'est dommage parce que mon implémentation des opérations élémentaire est intéressante.

**PRomu@ld** · 28/08/2008, 10h34

Juste quelques petites remarques sur le code en lui même.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

#include <stdlib.h>

En c++ il vaut mieux utiliser <cstdlib> (d'ailleurs il faut sinon tu inclues un fichier d'entête c et pas c++)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

using namespace std;

Dans un .h c'est pas conseillé.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

exposant_multiple(exposant_multiple &other);

Je suis maniaque mais il vaudrait mieux utiliser un const pour décrire le paramètre du constructeur de copie. D'ailleurs au passage, il y a plein d'endroits où tu peux utiliser des const.

De même dans le corps des constructeurs, tu peux utiliser des listes d'initialisation, c'est mieux.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
template <typename T>
polynome<T>& polynome<T>::operator= (polynome<T>& other)
{
    nombre_de_termes=other.nombre_de_termes;
    termes=other.termes;
    return *this;
}

Tu as une possible fuite mémoire ici.

Enfin :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
template <typename T>
bool polynome<T>::est_propre()
{
    if (nombre_de_termes<=1)
        return true;
    for (unsigned int i=0; i<nombre_de_termes;i++)
        if (termes[i].coefficient==0)
            return false;
    return true;
}

Tu as une comparaison douteuse. Si tu as des réels, une comparaison à zéro devrait se faire à un epsilon. Le mieux est tout de même d'utiliser des traits pour effectuer les comparaisons en fonction du type T.

Voilà pour mes petites remarques sur le code, il y en a sûrement d'autres, je n'ai pas regardé dans le détail.

Sinon, merci pour la contribution.

**Zavonen** · 24/09/2008, 07h12

Envoyé par PRomu@ld

Juste quelques petites remarques sur le code en lui même.

Vu ton message ce jour. Remarques toutes parfaitement justifiées, sauf peut être la dernière c'est bien la nullité absolue que je veux tester et non à epsilon près et dans tous les cas. Merci.

[maths] Polynômes à un nombre quelconque de variables

Contribuez

Discussions similaires

Partager

Partager