Polynômes, dépassement de mémoire

Marsh Posté le 04-06-2008 à 21:09:07

Bonjour,

Je réalise un programme en C qui réalise des opérations sur des polynômes définis tels que :

Code :

typedef unsigned int uint;
struct Polynome /*On définit la structure polynome */
{
uint Degre; /* Un entier non signé pour le degré */
double *Coefficients; /* Un tableau de double pour les coefficients */
};

La plupart des fonctions fonctionnent (enregistrement d'un polynome, chargement à partir d'un fichier binaire, lecture d'un fichier binaire, calcul en x=?, dérivé, etc...).

J'ai cependant un problème lorsque je calcul le signe avec ma fonction double Eval(struct Polynome *p, double x) qui me calcul la valeur du polynôme en un point.
J'utilise la fonction Roots pour calculer approximativement quand le polynôme s'annule. Cette fonction fait appel à Eval et il n'y a pas de problèmes. Cependant lorsque j'appelle de nouveau Eval dans une autre fonction, ça plante. Eval veut lire un polynôme à une adresse nulle... Pourquoi ?
La fonction Sign prend "mal" mon polynome en argument (Breakpoint 1, Sign (p=0x0, x1=-5, x2=5) at aau.c:242), Pourquoi ?

Le programme est compilé avec ces options : gcc -g aau.c -o aau -lm -Wall
La sortie du gdb :

Code :

Starting program: /home/yoyo/c/aau/aau
Groupe2
############
On declare un polynome p1
On declare un polynome p2 demande à l'utilisateur
Quel est le degre du polynome ? : 2
Coefficient 0 : 2
Coefficient 1 : 3
Coefficient 2 : -2
On declare un polynome p3 charge a partir d'un fichier
1.000000 + 2.000000 x + 3.000000 x^2 + 4.000000 x^3 + 5.000000 x^4 + 6.000000 x^5
On declare un polynome p4=p1*p2
4.000000 + 12.000000 x + 1.000000 x^2 - 12.000000 x^3 + 4.000000 x^4
########f(-0.500000)=0.000000 out[0]=-0.500000
########f(2.000000)=-0.000000 out[1]=2.000000
On affiche le signe de p4 sur [-5;5]
Breakpoint 1, Sign (p=0x0, x1=-5, x2=5) at aau.c:242
242 out[N]=Roots(p,x1,x2,out);
(gdb) s
Roots (p=0x0, x1=-5, x2=5, out=0xbf8c4fc8) at aau.c:186
186 int n=0;
(gdb) s
187 int signe=0,signeavant=0,j;
(gdb) s
188 double i=0.;
(gdb) s
189 if(Eval(p,x1)>0)
(gdb) s
Eval (p=0x0, x=-5) at aau.c:175
175 double out=0;
(gdb) s
177 for(i=0;i<=p->Degre;i++)
(gdb) s
Program received signal SIGSEGV, Segmentation fault.
0x08048a31 in Eval (p=0x0, x=-5) at aau.c:177
177 for(i=0;i<=p->Degre;i++)
(gdb) print p
$1 = (struct Polynome *) 0x0
(gdb)

Le programme :

Code :

/*
*
* Groupe 2
* Vim 7.1.138
* gcc 4.2.3
*/
#include <stdio.h> /*On inclue les librairies standards */
#include <math.h>
#include <stdlib.h>
#include <float.h>
#define N 100
typedef unsigned int uint; /*On définit les entiers non signés par uint*/
struct Polynome /*On définit la structure polynome */
{
uint Degre; /* Un entier non signé pour le degré */
double *Coefficients; /* Un tableau de double pour les coefficients */
};
// Fonctions donnees
double Pow(double x, uint p);
struct Polynome *Allocate(unsigned int degre);
void Delete(struct Polynome *p);
void Display(struct Polynome *p);
struct Polynome *Multiply(struct Polynome *p1, struct Polynome *p2);
// Fonctions a completer
struct Polynome *Prompt(void);
struct Polynome *Load(char *filename);
void Save(struct Polynome *p, char *filename);
double Eval(struct Polynome *p, double x);
uint Roots(struct Polynome *p, double x1, double x2, double *out);
struct Polynome *Derivate(struct Polynome *p);
void Sign(struct Polynome *p, double x1, double x2);
void Variation(struct Polynome *p, double x1, double x2);
double Eval(struct Polynome *p, double x)
{
double out=0;
int i;
for(i=0;i<=p->Degre;i++)
{
out=out+p->Coefficients[i]*pow(x,(float)i);
}
return out;
}
uint Roots(struct Polynome *p, double x1, double x2, double *out)
{
int n=0;
int signe=0,signeavant=0,j;
double i=0.;
if(Eval(p,x1)>0)
signeavant=1;
else
signeavant=0;
for(j=0;j<N;j++)
out[j]=0.0;
for(i=x1+0.0000001;i<x2;i+=0.0000001)
{
if(Eval(p,i)>0)
signe=1;
else
signe=0;
if(signeavant!=signe)
{
out[n]=i;
printf("########f(%lf)=%lf out[%d]=%lf\n",i,Eval(p,i),n,out[n]);
n++;
}
//printf("#f(%lf)=%lf ; signeavant=%dsigne=%d\n",i,Eval(p,i),signeavant,signe);
signeavant=signe;
}
/*for(j=0;j<N;j++)
{
printf("sol[%d]=%lf\n",j,out[j]);
}*/
return out[100];
}
void Sign(struct Polynome *p, double x1, double x2)
{
double out[N];
out[N]=Roots(p,x1,x2,out);
}
int main(int argc, char **argv)
{
printf("\n\nGroupe2\n############\n" );
printf("On declare un polynome p1\n" );
struct Polynome *p1;
p1=Allocate(2);
p1->Degre=2;
p1->Coefficients[0]=2;
p1->Coefficients[1]=3;
p1->Coefficients[2]=-2;
printf("On declare un polynome p2 demande à l'utilisateur\n" );
struct Polynome *p2;
p2=Prompt();
printf("On declare un polynome p3 charge a partir d'un fichier\n" );
struct Polynome *p3;
p3=Load("aau.dat" );
Display(p3);
printf("On declare un polynome p4=p1*p2\n" );
struct Polynome *p4;
p4=Allocate((p1->Degre)+(p2->Degre));
p4=Multiply(p1,p2);
Display(p4);
double out[N];
//int i;
out[N]=Roots(p1,-3,3,out);
/*for(i=0;i<N;i++)
{
printf("Racine %d : %lf\n",i,sol[i]);
}*/
printf("\nOn affiche le signe de p4 sur [-5;5]\n" );
Sign(p4,-5,5);
Delete(p1);
Delete(p2);
Delete(p3);
Delete(p4);
return 0;
}

Edit : c'ets vrai c'était un peu long...

Message édité par 2xyo le 04-06-2008 à 21:25:38

---------------
2 * yo = yoyo

Reply

Marsh Posté le 04-06-2008 à 21:09:07

Reply

Marsh Posté le 04-06-2008 à 21:14:38

T'avais pas plus long à nous faire lire ?

Et si tu sabrais tout ce qui ne change rien au problème et que tu nous montrais le code complet le plus simple qui provoque le problème ?

Reply

Marsh Posté le 04-06-2008 à 22:15:28

Ton code est imbitable, buffer overflow, tableau inutile, indentation bordélique, pas étonnant que tu passes des heures à débugger ce foutoir.

Pour info, ton erreur se situe certainement à la ligne 128 :

Code :

double out[N];
out[N]=Roots(p1,-3,3,out);

En déclarant ton tableau de N cases et affectant dans la N+1 ème case, tu écrase en fait la variable locale précendante de ton programme (du fait que sur la pile les variables sont empilés les unes sur les autres) qui est ... ton pointeur p4.

Par un concours de cirsconstance que j'ignore, mais à ce niveau on s'en tape, p4 se retrouve initialisé à 0, valeur transmise à Sign, puis transmise à Eval, puis ... SEGFAULT.

Message cité 1 fois
Message édité par tpierron le 04-06-2008 à 22:18:06

Reply

Marsh Posté le 04-06-2008 à 22:44:04

tpierron a écrit :

Ton code est imbitable, buffer overflow, tableau inutile, indentation bordélique, pas étonnant que tu passes des heures à débugger ce foutoir.

La structure du code nous a été fournie par nos professeurs . (J'ai évidement ajouté pas mal de bordel). L'indentation, c'est le copier coller qui a foiré...

tpierron a écrit :

Pour info, ton erreur se situe certainement à la ligne 128 :

Code :

double out[N];
out[N]=Roots(p1,-3,3,out);

En déclarant ton tableau de N cases et affectant dans la N+1 ème case, tu écrase en fait la variable locale précendante de ton programme (du fait que sur la pile les variables sont empilés les unes sur les autres) qui est ... ton pointeur p4.

Par un concours de cirsconstance que j'ignore, mais à ce niveau on s'en tape, p4 se retrouve initialisé à 0, valeur transmise à Sign, puis transmise à Eval, puis ... SEGFAULT.

Je vais méditer ça, mais je n'ai pas très bien compris à première vue comment y remédier... Je repasse dans une heure ou deux :sleep:
P.S : J'ai eu en consigne :

Citation :

uint Roots(struct Polynome *p, double x1, double x2, double *out)
Les racines seront stockées dans le tableau dont l'adress out est également passée en paramètre et dont l'allocation statique aura été faite ailleurs que dans cette fonction. cette fonction retournera le nombre de racines effectivement trouvées dans l'intervalle

P.S 2 : J'ai un problème en ammont qui n'arrange pas les choses :

Code :

On affiche le signe de p4 sur [-5;5]
########f(-0.500000)=0.000000 out[0]=-0.500000
########f(-0.499990)=0.000000 out[1]=-0.499990
########f(2.000000)=0.000000 out[2]=2.000000
########f(2.000010)=0.000000 out[3]=2.000010
Segmentation fault

Je viens juste de me rappeler à peu prêt comment on compare des float....Et je n'avais pas fait comme ça...

---------------
2 * yo = yoyo

Reply

Marsh Posté le 04-06-2008 à 23:33:26

J'ai changé quelques petits trucs tel que :
Le calcul des valeurs en 0 :

Code :

uint Roots(struct Polynome *p, double x1, double x2, double *out)
{
int n=0;
double i;
for(i=x1+0.00001;i<=x2;i+=0.00001)
{
if(fabs(Eval(p,i))<=fabs(Eval(p,i))*FLT_MIN){
out[n]=i;
printf("#f(%lf)=%lf out[%d]=%lf\n",i,Eval(p,i),n,Eval(p,i));
n++;
}
}
return out[100];
}

L'appel de mes fonctions dans le main

Code :

double out[N];
out[N]=Roots(p4,-5,5,out);
printf("\nOn affiche le signe de p4 sur [-5;5]\n" );
Sign(p4,-5,5);

Un peu de débugage :

Code :

Breakpoint 1, Sign (p=0x0, x1=-5, x2=5) at aau.c:216
216 out2[N]=Roots(p,x1,x2,out2);
(gdb) s
Roots (p=0x0, x1=-5, x2=5, out=0xbfa46148) at aau.c:186
186 int n=0;
(gdb)

Et là, j'ai les yeux embrouillés....

Message édité par 2xyo le 04-06-2008 à 23:33:54

---------------
2 * yo = yoyo

Reply

Marsh Posté le 05-06-2008 à 00:58:51

Je lui ai pété un EPSILON dans la gueule :love:

---------------
2 * yo = yoyo

Reply

Marsh Posté le 05-06-2008 à 01:44:18

Youhou, ça marche... (Enfin pour une valeur précise d'EPSILON avec un polynome particulier...)

Reply

Marsh Posté le 05-06-2008 à 09:03:51

montre le code de ton Allocate qu'on rigole ?

Message cité 1 fois

Reply

Marsh Posté le 05-06-2008 à 15:13:02

Ce code est une horreur :sweat: , ouvre un bouquin sur les bases du C (chapître tableau) ou (on peut réver) lis les réponses postées.

Code :

#define N 100
// .....
return out[100];
// .....
double out[N];
out[N]=Roots(p4,-5,5,out);

À la limite change au moins la déclaration de "out" en :

Code :

double out[N + 1];

Message cité 1 fois

Reply

Marsh Posté le 05-06-2008 à 15:43:28

Taz a écrit :

montre le code de ton Allocate qu'on rigole ?

Cette fonction vient de ce professeur http://perso.univ-rennes1.fr/jean-claude.nunes/

Code :

struct Polynome *Allocate(unsigned int degre)
{
struct Polynome *out;
out = (struct Polynome *) malloc(sizeof(struct Polynome));
out->Degre = degre;
out->Coefficients = (double *) malloc((degre + 1) * sizeof(double));
return out;
}

C'est si drôle que ça ?

tpierron a écrit :

Ce code est une horreur :sweat: , ouvre un bouquin sur les bases du C (chapître tableau) ou (on peut réver) lis les réponses postées.

Code :

#define N 100
// .....
return out[100];
// .....
double out[N];
out[N]=Roots(p4,-5,5,out);

À la limite change au moins la déclaration de "out" en :

Code :

double out[N + 1];

Ce N+1 ne changerai rien. En effet, la fonction Roots était erroné et renvoyait plusieurs centaines de racines dans le tableau (avec N=10)...Il y avait juste un problème de calibration de la fonction Roots pour déterminer à partir de quand on détectait une racine assez proche de 0 pour être considérer égale à 0 (et par conséquent être enregistrer comme racine dans out[N]).

Enfin, je ne voie pas trop l'intérêt de remarques comme ça "(on peut réver)"... (Tu as peut-être quelques connaissance en C mais cela ne te dispense pas d'un minimum de courtoisie)

---------------
2 * yo = yoyo

Reply

Marsh Posté le 05-06-2008 à 15:43:28

Reply

Marsh Posté le 05-06-2008 à 16:04:22

Petit test. Quoi que fasse la fonction Roots, ce code est foireux :

Code :

double out[N];
out[N]=Roots(p4,-5,5,out);

Tu n'as pas l'air de t'en rendre compte. On t'as donné la réponse, et t'as reposté un nouveau code avec la même annerie. Conclusion: tu ne lis pas les réponses ou tu ne les comprends pas, dans ce cas pose d'autres questions.

Message cité 1 fois

Reply

Marsh Posté le 06-06-2008 à 22:18:19

tpierron a écrit :

Petit test. Quoi que fasse la fonction Roots, ce code est foireux :

Code :

double out[N];
out[N]=Roots(p4,-5,5,out);

Tu n'as pas l'air de t'en rendre compte. On t'as donné la réponse, et t'as reposté un nouveau code avec la même annerie. Conclusion: tu ne lis pas les réponses ou tu ne les comprends pas, dans ce cas pose d'autres questions.

Code :

double out[N+1];
uint racine;
racine=Roots(p1,-1.0,3,out,0.1);

Autant pour moi. Le manque de sommeil, la mauvaise compréhension du prototype de Roots() et mes "connaissances" en C ne m'ont pas beaucoup aidé sur ce coup :whistle: (Je ne poste pas pour le plaisir de poster, par conséquent, je regarde quand même les réponses)

Code :

uint Roots(struct Polynome *p, double x1, double x2, double *out, double pas) /*On a modifier le protoype de Roots (cf compte rendu pour plus de dÃ©tail) et ajoutÃ© un pas d'avancement*/
{
for(j=0;j<N;j++) /*On parcour le tableau qui contiendra les racines */
out[j]=fabs(0.0); /*Et on l'initialise Ã 0.0 */
for(i=x1+pas;i<=x2;i+=pas) /*On "avance" sur la courbe de "pas" */
{
if(fabs(Eval(p,i))<=EPSILON){ /*On calcul alors la valeur absolu et si elle est plus petite que notre marge d'erreur maximum EPSILON */
}
}
return n; /*On retourne le nombre de racines */
}

P.S : L'indentation de ce forum est #@'é')'é :kaola:

---------------
2 * yo = yoyo

Reply

Marsh Posté le 07-06-2008 à 15:03:29

Code :

struct Polynome *Allocate(unsigned int degre)
{
struct Polynome *out;
out = malloc(sizeof(struct Polynome));
out->Degre = degre;
out->Coefficients = (double *) malloc((degre + 1) * sizeof(double));
return out;
}

Oui on peut rigoler effectivement :
Une erreur : une précaution indispensable est de vérifier le retour du malloc, on ne sait jamais, le retour peut-être NULL auquel cas ton programme plante.
Une maladresse, mais là certains en discutent, en C, on ne caste pas en général le retour de malloc, il peut masquer l'oubli d'inclusion du .h déclarant la fonction malloc.
ton code corrigé pourrait donner ceci :

Code :

struct Polynome *Allocate(unsigned int degre)
{
struct Polynome *out;
out = (struct Polynome *) malloc(sizeof(struct Polynome));
if (out != NULL)
{
out->Degre = degre;
out->Coefficients = malloc((degre + 1) * sizeof(double));
if (out->Coefficients == NULL)
{
// a toi de voir ce que tu veux faire
}
}
else
{
// a toi de vir ce que tu veux faire
}
return out;
}

Message édité par Trap D le 07-06-2008 à 15:06:09

Reply

Polynômes, dépassement de mémoire

Sujets relatifs:

Leave a Replay