IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Factorielle sur de grands entiers : erreur de segmentation


Sujet :

C

  1. #1
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mai 2009
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2009
    Messages : 6
    Points : 1
    Points
    1
    Par défaut Factorielle sur de grands entiers : erreur de segmentation
    Bonjour,
    j'ai un projet de C qui consiste à faire des calculs sur de grands entier (au delà de 64bits), les opérations à implémenter sont *,/,+,-,! et c'est sur la factorielle que je rencontre des problèmes (multiplication & soustrait fonctionnentnt), elle fonctionne jusqu'à !99 mais me génère une erreur de segementation à partir de !100.

    Voici ma fonction factorielle:
    Code : 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
    bigint factorielle(bigint);
     
    bigint factorielle(bigint nb1)
    {
    bigint tmp,resultat,sous;
     
    tmp=(bigint)malloc(sizeof(struct biginteger));
    tmp=nb1;
     
    resultat=(bigint)malloc(sizeof(struct biginteger));
    resultat->digits=(char *)malloc(1000);
    resultat=nb1;
     
     
    //bigint de valeur 1 qui servira à décrémenter nb1
    sous=(bigint)malloc(sizeof(struct biginteger));
    sous->taille=1;
    sous->digits[0]='1';
     
    //tant que tmp ne vaut pas 1
    while(tmp->taille!=1 || tmp->digits[0]!='1')
    {
    //On le décrémente et on le multiplie par le résultat précédent
    tmp=soustrait(tmp,sous);
    trim(&tmp);
    resultat=multiplication(resultat,tmp);
    }
    return resultat;
    }

    Et ma stucture bigint, digits est un pointeur de caractère permettant d'implémenter mon entier.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    struct biginteger {
    	char * digits;
    	int taille;
    	char signe;
    	};
     
    typedef struct biginteger * bigint;
    Quelqu'un aurait une idée du problème ??? Merci d'avance

  2. #2
    Membre confirmé Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Points : 633
    Points
    633
    Par défaut
    Salut, ne voit tu pas une contradiction là :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    tmp=(bigint)malloc(sizeof(struct biginteger));
    tmp=nb1;
    et là :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    resultat=(bigint)malloc(sizeof(struct biginteger));
    ...
    resultat=nb1;
    ?
    The mark of the immature man is that he wants to die nobly for a cause, while the mark of the mature man is that he wants to live humbly for one.
    --Wilhelm Stekel

  3. #3
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mai 2009
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2009
    Messages : 6
    Points : 1
    Points
    1
    Par défaut
    erf, oui en effet il n'y a pas besoin d'allouer tmp et resultat, mais le problème reste le même

  4. #4
    Membre confirmé Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Points : 633
    Points
    633
    Par défaut
    As tu pensé au problème de dépassement ?
    The mark of the immature man is that he wants to die nobly for a cause, while the mark of the mature man is that he wants to live humbly for one.
    --Wilhelm Stekel

  5. #5
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mai 2009
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2009
    Messages : 6
    Points : 1
    Points
    1
    Par défaut
    Tu pourrais développé ta réponse ??? J'ai pas tout à fait acquis toutes ces notions (J'ai commencé le C cette année donc c'est encore plutôt confus en ce qui concerne certaines choses)

  6. #6
    Membre confirmé Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Points : 633
    Points
    633
    Par défaut
    Ben 100!, il te faut 2 chiffre de plus que pour 99!. Donc deux cases en plus si j'ai bien compris ce que tu fais. En gors, il se peut que tu est besoin de redimensionné ton tableau.

    => il faut 157 digit pour 100!.
    The mark of the immature man is that he wants to die nobly for a cause, while the mark of the mature man is that he wants to live humbly for one.
    --Wilhelm Stekel

  7. #7
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mai 2009
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2009
    Messages : 6
    Points : 1
    Points
    1
    Par défaut
    Oui, c'est géré directement dans la fonction multiplication donc de ce côté il n'y a pas de problème

  8. #8
    Membre confirmé Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Points : 633
    Points
    633
    Par défaut
    Hum...
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    resultat->digits=(char *)malloc(1000);
    ...
     
    sous=(bigint)malloc(sizeof(struct biginteger));
    sous->taille=1;
    sous->digits[0]='1'; // Double Hum
    The mark of the immature man is that he wants to die nobly for a cause, while the mark of the mature man is that he wants to live humbly for one.
    --Wilhelm Stekel

  9. #9
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mai 2009
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2009
    Messages : 6
    Points : 1
    Points
    1
    Par défaut
    Je ne vois pas où est le problème ma variable sous est simplement un bigint de valeur 1 permettant de décrémenter tmp, et à prioris il ne pose pas de problème car la décrémentation fonctionne, c'est le fait que 1 soit attribué sous forme de caractère qui te choques ?

  10. #10
    Membre confirmé Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Points : 633
    Points
    633
    Par défaut
    Non, c'est le faite que tu n'alloue pas l'espace mémoire de digit, et que tu écrive dans digit[0] qui n'est pas alloué.
    The mark of the immature man is that he wants to die nobly for a cause, while the mark of the mature man is that he wants to live humbly for one.
    --Wilhelm Stekel

  11. #11
    Nouveau Candidat au Club
    Profil pro
    Inscrit en
    Mai 2009
    Messages
    6
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2009
    Messages : 6
    Points : 1
    Points
    1
    Par défaut
    OK c'est corrigé mais j'ai toujours le même problème.


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    sous=(bigint)malloc(sizeof(struct biginteger));
    sous->taille=1;
    sous->digits=(char *)malloc(1);
    sous->digits[0]='1';
    j'ai affiché la valeur de mon tmp après chaque décrémentation pour tester ce qui me donne pour !99 : 98,97,96...,1
    et pour !100 j'ai : 1/9, 1/8, 1/7, 1/6, 1/5, 1/4...
    C'est bizarre autant qu'étrange

  12. #12
    Membre confirmé Avatar de Lavock
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    560
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2009
    Messages : 560
    Points : 633
    Points
    633
    Par défaut
    Ben le problème est ailleurs...
    The mark of the immature man is that he wants to die nobly for a cause, while the mark of the mature man is that he wants to live humbly for one.
    --Wilhelm Stekel

  13. #13
    Membre à l'essai
    Profil pro
    Inscrit en
    Octobre 2009
    Messages
    16
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Meurthe et Moselle (Lorraine)

    Informations forums :
    Inscription : Octobre 2009
    Messages : 16
    Points : 19
    Points
    19
    Par défaut
    Bonjour,

    En regardant les bouts de codes les un à la suite des autres, j'ai peut-être une piste qui peut t'aider :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    tmp=(bigint)malloc(sizeof(struct biginteger)); // aucun malloc de digits
    tmp=nb1;
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    sous=(bigint)malloc(sizeof(struct biginteger));
    sous->taille=1;
    sous->digits=(char *)malloc(1);
    sous->digits[0]='1';
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    resultat=(bigint)malloc(sizeof(struct biginteger));
    resultat->digits=(char *)malloc(1000);
    resultat=nb1;
    Je ne me souviens plus trop du comportement des pointeurs dans une structure (ca fait 2ans que j'ai pas touché de la progra je m'y remets seulement, c'est comme le vélo, il paraît que ça s'oublie pas ), mais l'un des deux cas suivants se présente (je ne me souviens plus, Honte !!! Honte !!! Harot sur l'hérétique !!! ) :
    - Quand tu fais "tmp=nb1" ou "resultat=nb1" tes mallocs n'ont servi à rien (à par créer une fuite mémoire pour le troisième bout de code cité ) car tes "digits" pointent au même endroit. Avec le risque suivant : quand tu modifies les valeurs du "digits" d'une des structs, les valeurs du "digits" de l'autre struct est aussi modifé.
    - Ou tu risques le dépassement de mémoire si la mémoire allouée au "digits" de "nb1" est supérieure à la mémoire allouée au "digits" de "tmp" ou de "résultat". En effet on voit que tu n'alloues pas forcément la même taille à chaque fois.

    J'aimerais pouvoir te confirmer quel cas est le bon, mais je n'ai pas de quoi tester sur ce poste.


    Comme dit avant, ça fait un moment que j'ai pas toucher de progra, donc je peux me tromper (et y'aura donc sûrement du monde pour choisir le bon cas et/ou corriger les bêtises que j'ai pu dire), voilà juste une piste à suivre.

    J'ai jamais été fan de l'affectation de deux structs ensemble par l'opérateur '='. Je préfère utiliser une fonction qui s'occupe de ça en faisant les affectation champ par champ ainsi que les contrôles nécessaires sur la mémoire. Dans le cas de champs à pointeur, s'assurer que la mémoire allouée est suffisante et faire des memcpy() ou une fonction équivalente de ton cru. Ca implique aussi du coup de modifier l'ensemble de ton programme pour chaque affectation.

    En espérant que ça puisse te guider vers la résolution de ton problème.
    Courage .

  14. #14
    Expert éminent sénior
    Avatar de diogene
    Homme Profil pro
    Enseignant Chercheur
    Inscrit en
    Juin 2005
    Messages
    5 761
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Enseignant Chercheur
    Secteur : Enseignement

    Informations forums :
    Inscription : Juin 2005
    Messages : 5 761
    Points : 13 926
    Points
    13 926
    Par défaut
    J'aimerais pouvoir te confirmer quel cas est le bon, mais je n'ai pas de quoi tester sur ce poste.
    C'est le cas 1 :
    - Quand tu fais "tmp=nb1" ou "resultat=nb1" tes mallocs n'ont servi à rien (à par créer une fuite mémoire pour le troisième bout de code cité )
    et la fuite existe aussi pour le premier code

    On ne doit jamais écrire
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
     truc = malloc(.....)
     truc = machin;

    J'ai jamais été fan de l'affectation de deux structs ensemble par l'opérateur '='.
    ca ne pose pas de problèmes sauf si de l'allocation dynamique a été faite et l'adresse rangée dans la structure : l'adresse est copiée, mais pas le contenu du tableau alloué qui devient alors commun aux deux structures.
    Publication : Concepts en C

    Mon avatar : Glenn Gould

    --------------------------------------------------------------------------
    Une réponse vous a été utile ? Remerciez son auteur en cliquant le pouce vert !

  15. #15
    Modérateur
    Avatar de Obsidian
    Homme Profil pro
    Développeur en systèmes embarqués
    Inscrit en
    Septembre 2007
    Messages
    7 360
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : Développeur en systèmes embarqués
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2007
    Messages : 7 360
    Points : 23 600
    Points
    23 600
    Par défaut
    Bonsoir,

    Citation Envoyé par ELCourtez Voir le message
    Code C : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    tmp=(bigint)malloc(sizeof(struct biginteger));
    tmp=nb1;
     
    resultat=(bigint)malloc(sizeof(struct biginteger));
    resultat->digits=(char *)malloc(1000);
    resultat=nb1;
    Je peux me tromper, mais tout cela ressemble à de mauvaises habitudes prises en Java. Si tu veux copier un de tes bigint dans un autre, tu peux essayer « *tmp = *nb1 », mais tu auras d'autres ennuis, étant donné que tes structures embarquent des pointeurs elles aussi.

    Ça, ça sent mauvais. « &tmp » est un pointeur sur un pointeur. Ce n'est donc pas l'adresse du nombre que tu désignes par tmp, mais l'adresse du pointeur qui pointe dessus. Et c'est dû à ce qui suit :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    typedef struct biginteger * bigint;
    Cacher la nature d'un pointeur dans un typedef est presque toujours source d'ennuis. Spécialement quand on débute. Je pense d'ailleurs que la tous tes soucis viennent de là.

    En tout état de cause, le plantage a toutes les chances d'avoir lieu dans tes fonctions de calcul (soustrait(), multiplication() et autres). Il faut donc que tu nous les déposes ici pour qu'on les examine.

    Je pense aussi que tes routines fonctionnent par hasard : il est bien possible qu'il y ait des dépassements de tableau avec les autres valeurs de ta factorielle, même si le système alloue des segments suffisamment grands pour qu'il ne se passe rien.

Discussions similaires

  1. petit problème sur les grand entiers en c
    Par abdou4101 dans le forum C
    Réponses: 4
    Dernier message: 01/05/2010, 21h00
  2. Division sur de Grands entiers
    Par mawguai dans le forum Mathématiques
    Réponses: 4
    Dernier message: 06/06/2008, 22h08
  3. Réponses: 23
    Dernier message: 08/01/2006, 23h59
  4. Erreur de segmentation sur une chaine en récursif...
    Par laurent_ifips dans le forum C
    Réponses: 12
    Dernier message: 13/12/2005, 17h04
  5. Opération sur de grands entiers
    Par tutu dans le forum C
    Réponses: 16
    Dernier message: 24/05/2005, 09h56

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo