addtion

addtion - C - Programmation

Marsh Posté le 31-01-2007 à 14:41:57    

bonjour,
pour m'amuser j'ai fais un programme ,qui calcule la suite de fibonnaci,dont voici le code :

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. int main(void)
  5. {
  6.   int limite,i;
  7.   int *fibo,*temp; //initialisation des pointeurs
  8.   char tampon[16]; //tampon pour capture au clavier --> 16 caractères max
  9.   printf("Combien d'iteration ? :" );
  10.   fgets(tampon, 16, stdin); //on envoie l'entrée standard (stdin) dans le tampon
  11.   sscanf(tampon, "%d", &limite); //on lit la valeur du tampon que l'on stocke dans limite
  12.   fibo     = calloc(2, sizeof(int)); //on alloue de la memoire pour un array de 2 entier
  13.   //printf("memoire allouee : %d octet\n",(2 * sizeof(int)));
  14.   fibo[0]  =1;
  15.   fibo[1]  =1;
  16.   printf("%d; iteration 0\n%d; iteration 1\n",fibo[0],fibo[1]);
  17.   for(i=2;i<limite;i++)
  18.    {
  19.     //printf("reallocation de memoire : %d octet\n",(i * sizeof(int)));
  20.     temp    = realloc(fibo, (i+1) * sizeof(int)); //on tente d'ajouter une case au tableau ...
  21.     if(temp == NULL) {printf("erreur de realloctaion de memoire" );} //ça rate ----> exit
  22.     else {temp=fibo;}                                               //ça réussi ---> on continue !!
  23.     fibo = fibo[i-1] + fibo[i-2]; //le coeur du programme !!!!
  24.     printf("fibo[i]= %d+%d=%d; iteration %d \n",fibo[i-1],fibo[i-2],fibo[i],i);
  25.     //if(fibo[i]>limite) break; //si le nombre trouvé est > ou =à la limite on stop
  26.    }
  27.   printf("memoire allouee : %d octet\n",(i * sizeof(int)));
  28.   free(fibo); //on libère la memoire
  29. }
 

sauf que à la 44ème boucle, le programme ne sais plus faire une addition !! il me sort un résultat négatif alors que les deux termes sont positifs ! puis alterne positif/négatif comme bon lui semble :pt1cable: donc j'ai remplacé tous les [i]int par des unsigned int que j'ai remplacer par des long puis par des unsigned long.
je ne vois pas dutout d'où vient ce problème !!
merci d'avance :jap:

Message cité 1 fois
Message édité par nicodu95 le 31-01-2007 à 14:54:18
Reply

Marsh Posté le 31-01-2007 à 14:41:57   

Reply

Marsh Posté le 31-01-2007 à 15:01:53    

Salut,
 

Code :
  1. temp    = realloc(fibo, (i+1) * sizeof(int)); //on tente d'ajouter une case au tableau ...
  2.     if(temp == NULL) {printf("erreur de realloctaion de memoire" );} //ça rate ----> exit
  3.     else {temp=fibo;}


 
Ca serait pas plutôt fibo=temp ?
 
Sinon, je pense que c'est bien un dépassement de capacité sachant que int = long sous système 32 bits et qu'on ne peut pas additionner des nombres indéfiniment.


Message édité par anordem le 31-01-2007 à 15:03:40
Reply

Marsh Posté le 31-01-2007 à 15:13:55    

2^32 = 4 294 967 296 alors que le résultat de l'opération demandé boucle 44 (où ça bug) est
1836311903 +1134903170 = 2 971 215 073  :heink:

 

edit : même une calculatrice sait le faire :o

Message cité 1 fois
Message édité par nicodu95 le 31-01-2007 à 15:20:03
Reply

Marsh Posté le 31-01-2007 à 15:29:24    

ouais, mais 2^31=2 147 483 648
 
Donc pour peu que tu sois en signed long, ça passe plus.
 
Pour faire le test, essaie de voir ce que donne 2^32 + (le nombre négatif que tu obtiens)


---------------
TriScale innov
Reply

Marsh Posté le 31-01-2007 à 17:07:21    

Exact, et vu que le printf affiche des valeurs signées :

Code :
  1. printf("fibo= %d+%d=%d; iteration %d \n",fibo[i-1],fibo[i-2],fibo[i],i);


On obtient des valeurs négatives. Mais bon afficher des entiers non signés ne changent pas grand chose et on doit gagner une itération supplémentaire avant le débordement :
 
fibo= 1836311903+1134903170=2971215073;
fibo= 2971215073+1836311903=512559680;
 
Edit:
 

nicodu95 a écrit :

2^32 = 4 294 967 296 alors que le résultat de l'opération demandé boucle 44 (où ça bug) est  
1836311903 +1134903170 = 2 971 215 073  :heink:  
 
edit : même une calculatrice sait le faire :o


Ah, j'avais pas capté que c'est toi qui a créé le topic. Sympa ta façon de remercier ceux qui prennent la peine de répondre à tes questions...


Message édité par anordem le 31-01-2007 à 17:12:01
Reply

Marsh Posté le 31-01-2007 à 17:12:58    

dans mon printf j'ai remplacé le %d par %u et plus de problème  :jap:

Citation :

Ah, j'avais pas capté que c'est toi qui a créé le topic. Sympa ta façon de remercier ceux qui prennent la peine de répondre à tes questions...


si c'est à ça que tu répond (anordem) :

Citation :

edit : même une calculatrice sait le faire :o

sache que je voulais juste dire que comme une calculatrice sait le faire , sa serait étrange qu'un ordinateur ne le puisse pas  :)

 

merci à tous pour votre aide  :jap:  :jap:   :)

Message cité 1 fois
Message édité par nicodu95 le 31-01-2007 à 17:17:35
Reply

Marsh Posté le 31-01-2007 à 17:25:48    

nicodu95 a écrit :

dans mon printf j'ai remplacé le %d par %u et plus de problème  :jap:


 
Permet moi d'en douter. Tu as simplement supprimer le signe négatif mais tes valeurs sont fausses car
2.971.215.073 + 1.836.311.903 = 4.807.526.976 et pas 512.559.680
 
 
PS : l'humilité ne tue pas et être débutant n'est pas une tare.

Reply

Marsh Posté le 31-01-2007 à 19:40:01    

effectivement , tu as raison , le max que je peux faire est 44 boucle :(  

Message cité 1 fois
Reply

Marsh Posté le 31-01-2007 à 22:05:13    

nicodu95 a écrit :

effectivement , tu as raison , le max que je peux faire est 44 boucle :(


 
Utilises des "double" => tu passeras de 4 octets à 8. Et si ton compilo l'accepte, tente le "long double" et t'auras 10 octets pour t'amuser (de quoi aller probablement jusqu'à 50 boucles...)
 
Au fait, pourquoi tu fais un calloc de 2 puis du realloc à chaque boucle ? Tu pourrais pas faire directement un calloc de "limite" ??? Et d'ailleurs, pourquoi "calloc" alors que les seules valeurs que t'as besoin d'initialiser sont "fibo[0]" et "fibo[1]" ???
Fais donc un simple malloc !!!!

Message cité 1 fois
Message édité par Sve@r le 31-01-2007 à 22:09:09

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 31-01-2007 à 22:46:19    

Sve@r a écrit :

Utilises des "double" => tu passeras de 4 octets à 8. Et si ton compilo l'accepte, tente le "long double" et t'auras 10 octets pour t'amuser (de quoi aller probablement jusqu'à 50 boucles...)


Sauf que c'est des flottants...
Par contre en C99 y'a les long long (et sur la plupart des compilos pas-c99 y'a des __int64 qui trainent ou des trucs du genre)

Message cité 1 fois

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.
Reply

Marsh Posté le 31-01-2007 à 22:46:19   

Reply

Marsh Posté le 31-01-2007 à 23:07:26    

Mouais, enfin, toutes ces bidouilles ne résolvent pas vraiment le problème. :)
Une méthode plus élégante serait d'utiliser une biliothèque de BigNums, telle que Miracl par exemple http://www.shamus.ie/  

Reply

Marsh Posté le 01-02-2007 à 16:03:51    

0x90 a écrit :

Sauf que c'est des flottants...


Ben t'as quand-même le droit d'additionner des flottants, même si leur partie décimale est toujours à 0...


---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 10-02-2007 à 12:34:56    

nicodu95 a écrit :

Code :
  1. else {temp=fibo;}



a l'envers, ça tue...
Essaye ça
 

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>
  5. #ifdef WIN32
  6. #define LLU "I64u"
  7. #else
  8. #define LLU "llu"
  9. #endif
  11. int main (void)
  12. {
  13.    for (;;)
  14.    {
  15.       char tampon[8];           //tampon pour capture au clavier --> 16 caractères max
  16.       printf ("Combien d'iteration ? (ou 'q' pour quitter) :" );
  17.       fflush (stdout);
  18.       fgets (tampon, sizeof tampon, stdin); //on envoie l'entrée standard (stdin) dans le tampon
  19.       {
  20.          int iter;
  21.          int n = sscanf (tampon, "%d", &iter);
  22.          printf("n=%d\n", n);
  23.          if (n == 1) //on lit la valeur du tampon que l'on stocke dans limite
  24.          {
  25.             //on alloue de la memoire pour un array de 2 + iter entier
  26.             unsigned long long *fibo = malloc ((2 + iter) * sizeof *fibo);
  27.             if (fibo != NULL)
  28.             {
  29.                //printf("memoire allouee : %d octet\n",(2 * sizeof(int)));
  30.                fibo[0] = 1;
  31.                fibo[1] = 1;
  32.                printf ("%" LLU "; iteration 0\n"
  33.                        "%" LLU "; iteration 1\n", fibo[0], fibo[1]);
  34.                {
  35.                   int i;
  36.                   for (i = 2; i < iter; i++)
  37.                   {
  38.                      assert (i - 2 >= 0);
  39.                      assert (i < iter);
  41.                      fibo[i] = fibo[i - 1] + fibo[i - 2]; //le coeur du programme !!!!
  42.                      printf ("fibo[i]= %" LLU "+%" LLU "=%" LLU
  43.                              "; iteration %d \n", fibo[i - 1], fibo[i - 2],
  44.                              fibo[i], i + 1);
  45.                   }
  46.                }
  47.                free (fibo), fibo = NULL; //on libère la memoire
  48.             }
  49.             else
  50.             {
  51.                puts ("memory error" );
  52.             }
  53.             assert (fibo == NULL);
  54.          }
  55.          else
  56.          {
  57.             puts ("input error : bye" );
  58.             break;
  59.          }
  60.       }
  61.    }
  62.    return 0;
  63. }

Message cité 1 fois
Message édité par Emmanuel Delahaye le 10-02-2007 à 13:09:59

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Marsh Posté le 11-02-2007 à 12:55:37    

Emmanuel Delahaye a écrit :

Code :
  1. char tampon[8];           //tampon pour capture au clavier --> 16 caractères max



Faire rentrer 16 caractères (plus le '\0') dans un char[8]... Alors là, je pige que dalle sauf s'il sagit d'une erreur d'inattention comme ça arrive à tous => il n'y a pas longtemps, je voulais calculer la longueur d'une chaîne et rajouter 1 au résultat. Et j'ai tapé

Code :
  1. i=strlen(chaine + 1)

et j'ai galéré au-moins un quart d'heure à essayer de comprendre pourquoi mon programme plantait !!!  :sol:  
 
Sinon je ne trouve pas dans l'algo le test sur "q" pour quitter. Apparemment si on tape "q" (ou toute autre lettre), alors sscanf renverra 0 et il sortira sur le "input error : bye" non ???

Message cité 1 fois
Message édité par Sve@r le 11-02-2007 à 13:07:59

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 11-02-2007 à 15:18:58    

Sve@r a écrit :

Faire rentrer 16 caractères (plus le '\0') dans un char[8]... Alors là, je pige que dalle sauf s'il sagit d'une erreur d'inattention comme ça arrive à tous


 
Bah, j'ai réduit la taille du tableau sans modifier le commentaire. Shame on me...
 

Citation :


Sinon je ne trouve pas dans l'algo le test sur "q" pour quitter. Apparemment si on tape "q" (ou toute autre lettre), alors sscanf renverra 0 et il sortira sur le "input error : bye" non ???

Oui, je n'ai pas dit que seul 'q' permettait de sortir. Ne pas confondre l'absence de spèc avec l'aide à utilisateur !


---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed