Discussion :

[argon]

Bonjour tout le monde

J'ai un problème avec le calcul de la factoriel.

Voici le code, je ne mets que la fonction où il y a la boucle.

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
 
int factoriel(int m)
{
    int i;
 
    for(i=1;i<m;i++)
    {
 
    m = m*i;
 
    }
 
   printf("resulat %d\n", m); 
  return m;  
}

Il me sort des résultat négatif.

Pourquoi?

Merci.

Cordialement

A bientôt

[JeitEmgie]

Bonjour tout le monde

J'ai un problème avec le calcul de la factoriel.

Voici le code, je ne mets que la fonction où il y a la boucle.

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
 
int factoriel(int m)
{
    int i;
 
    for(i=1;i<m;i++)
    {
 
    m = m*i;
 
    }
 
   printf("resulat %d\n", m); 
  return m;  
}

Il me sort des résultat négatif.

Pourquoi?

Merci.

Cordialement

A bientôt

… overflow…

un "int" est stocké sur un nombre fini de bits (8, 16, 32, 64, 128 pour les architectures les plus courantes)
dès que le résultat est plus grand que le plus grand entier positif représentable sur le nombre de bits dédiés aux entiers "int" par votre architecture (hardware + compilateur), le résultat apparaîtra négatif…

vous gagnerez un peu "d'espace" en déclarant i et m "unsigned int",
ou encore "unsigned long long"…

mais pour calculer de très grand nombres il faut utiliser une bibliothèque adhoc… voir par exemple http://www.swox.com/gmp/

[Thierry Chappuis]

Salut,

Le problème vient du fait que tu utilises le paramètre m comme condition d'arrêt de ta boucle for, mais que m est également modifié dans le corps de ta boucle. Le code suivant fonctionne:

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
#include <stdio.h>
#include <stdlib.h>
 
int factoriel(int m)
{
    int i;
    int result = m;
 
    for (i = 1; i < m; i++)
    {
        result = result * i;
    }
 
    printf("resulat %d\n", result);
    return result;
}
 
int main(void)
{
    factoriel(3);
 
    return EXIT_SUCCESS;
}

Thierry

[Thierry Chappuis]

… overflow…

un "int" est stocké sur un nombre fini de bits (8, 16, 32, 64, 128 pour les architectures les plus courantes)
dès que le résultat est plus grand que le plus grand entier positif représentable sur le nombre de bits dédiés aux entiers "int" par votre architecture (hardware + compilateur), le résultat apparaîtra négatif…

vous gagnerez un peu "d'espace" en déclarant i et m "unsigned int",
ou encore "unsigned long long"…

mais pour calculer de très grand nombres il faut utiliser une bibliothèque adhoc… voir par exemple http://www.swox.com/gmp/

En l'occurence, il y avait overflow déjà avec l'appel factoriel(3). Le problème était un problème de logique et non d'entier signé ou non. Toutefois, il est vrai qu'on peut déclarer result comme unsigned int, celui-ci ne prenant jamais de valeur négative (c'est même préférable). En ce qui concerne i, ce n'est pas forcément nécessaire. Dans le calcul d'une factorielle, c'est surtout le résultat qui devient énorme.

Thierry

[souviron34]

oui dans ce cas-là moi je mettrais le résultat en double....

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
double factoriel(int m)
{
    int i;
    double result = (double)m;
 
    for (i = 1; i < m; i++)
    {
        result = result * (double)i;
    }
 
    printf("resultat %g\n", result);
    return result;
}

[Franck.H]

oui dans ce cas-là moi je mettrais le résultat en double....

Heu pas plutôt unsigned long ? double étant un nombre à virgule flottante et lui il est basé sur un int au départ.

[souviron34]

Heu pas plutôt unsigned long ? double étant un nombre à virgule flottante et lui il est basé sur un int au départ.

et ??

factorielle (255 ) doit bien dépasser les capacités d'un int ou long non ?
Suivant l'architecture c'est assez facile à calculer :

le max est soit 32 soit 64 bits pour un entier... donc 2^ 32 ou 64

je suppose donc (en gros, je vais pas me taper le calcul) que factorielle(66) dépasse les 64 bits..

[Thierry Chappuis]

et ??

factorielle (255 ) doit bien dépasser les capacités d'un int ou long non ?
Suivant l'architecture c'est assez facile à calculer :

le max est soit 32 soit 64 bits pour un entier... donc 2^ 32 ou 64

je suppose donc (en gros, je vais pas me taper le calcul) que factorielle(66) dépasse les 64 bits..

Tu as raison! Un entier, même de 64 bits, c'est ridicule pour calculer une factorielle...

Thierry

[Franck.H]

Ouais effectivement, j'avais pas vu ca sous cet angle

[Melem]

Comme mujigka l'a déja fait remarqué déja l'algorithme est faux. Théoriquement c'est même une boucle sans fin puisque m sera toujours supérieur a i. Bref, un code plus éfficace :

Code :

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

1
2
3
4
5
6
 
double factorielle(int n)
{
if (n == 0) return 1.0;
else return n * factorielle(n - 1);
}

Utilise %g dans printf pour afficher le résultat.

[millie]

Bref, un code plus éfficace :

Ici, ça va qu'il est peu probable que l'on fasse un appel avec une grosse valeur. Mais faire un nombre d'appel important (à cause de la définition récursive) peut être dangereux car il peut vite y avoir des dépassements de piles.

Maintenant, si tu fais un appel avec -1.0 dans ta fonction, là, tu auras à coup sur un beau stack overflow.


Un dépassement de pile serait encore plus susceptible d'arriver avec une fonction du genre :

Code :

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

1
2
3
4
5
6
7
long fonction(long n)
{
if (n <= 0) 
  return 0;
 else 
  return(1 + fonction(n - 1));
}

[Médinoc]

Pourquoi encore plus ?

[millie]

Enfin, je parlais dans la mesure ou la fonction fonctionne bien :

faire un appel à : fonction(1000000) retournera le bon résultat alors que l'appel à factoriel(1000000) ne retournera pas le bon (comme ça avait déjà été signalé).

Enfin, si on met une précondition supplémentaire afin que le résultat soit correcte, il faut énormement limiter l'espace de départ de la fonction factoriel. L'espace de départ de l'autre est pas contre beaucoup plus grand.

Je parlais qu'il y avait plus de chance de faire un dépassement de pile si l'on se retreint à ces espaces.

[Thierry Chappuis]

Bref, un code plus éfficace :

Plus efficace, vraiment?

Thierry

[souviron34]

Ici, ça va qu'il est peu probable que l'on fasse un appel avec une grosse valeur. Mais faire un nombre d'appel important (à cause de la définition récursive) peut être dangereux car il peut vite y avoir des dépassements de piles.
[/CODE]

Euh.. Pardon, mais il me semble que vu que le code ne fait pas d'allocation et n'a aucune variable "à lui", en quoi la taille de la pile est-elle importante ?? A la limite il y aura du swap, mais je vois pas pourquoi on ne pourrait pas faire 500 000 appels itératifs ??? (ou bien il y a quelque chose qui m'échappe, ce qui est fort possible )

[EDIT]

Mais bon tout ceci pour dire que la première version (aux détails réglés après près) est nettement plus effiicace quand même que celle de Melem..

[/EDIT]

[JeitEmgie]

Enfin, je parlais dans la mesure ou la fonction fonctionne bien :

faire un appel à : fonction(1000000) retournera le bon résultat alors que l'appel à factoriel(1000000) ne retournera pas le bon (comme ça avait déjà été signalé).
.

FYI,
100000! est déjà un nombre de 456.575 chiffres…
et 1000000! fait 5.565.710 chiffres…

[thewho]

Bonjour,

Code :

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

1
2
3
4
5
6
7
long fonction(long n)
{
if (n <= 0) 
  return 0;
 else 
  return(1 + fonction(n - 1));
}

...

faire un appel à : fonction(1000000) retournera le bon résultat alors que l'appel à factoriel(1000000) ne retournera pas le bon (comme ça avait déjà été signalé).

Certes, mais fonction ne calcule pas la factorielle, ou alors il faut que je retorune à l'école.

EDIT : D'ailleurs, en prenant le fait que le nombre d'atome dans l'univers est minoré par 2^100 et le fait que 100! est minoré par 2^100. On en déduit facilement :p que l'on ne pourra jamais calculer 100!. Donc au pire, il y aura 100 appels récursifs (même si on a une possibilité de représentation immense pour les entiers). Ca ne ferait que 100 éléments à peu près sur la pile. Donc, c'est fort respectable.

Parce que tu penses que le nombre de particules dans l'univers interdit l'utilisation de nombre plus grands ?

Pour quelle raison cela serait-il ?

100! est de l'ordre de 10^158.

Pour ta gouverne, les mathématiciens (essentiellement) de certains domaines utilisent assez régulièrement des nombres beaucoup plus, mais alors vraiment beaucoup plus grands.

Moi-même, j'utilise journellement des nombres de longueur moyenne 10^1000, et occasionnellement, jusqu'à 10^100000, et je ne suis qu'un modeste utilisateur par rapport à d'autres.

[millie]

J'ai oublié un 2^100. Je voulais dire qu'il n'est pas possible d'utiliser d'entier dont la representation binaire requiert plus de 2^100 bits, comme par exemple 2^2^100.

Donc, revois ton jugement avec ma correction

Certes, mais fonction ne calcule pas la factorielle, ou alors il faut que je retorune à l'école.

je n'ai jamais dit le contraire. J'ai dit qu'il etait plus probable de faire tout planter avec cette fonction si l'on se restreint à un espace de depart où la fonction donne un résultat correct. C'était juste un exemple pour montrer que certaines fonctions avec des appels récursifs peuvent facilement faire des dépassements de pile.

Euh.. Pardon, mais il me semble que vu que le code ne fait pas d'allocation et n'a aucune variable "à lui", en quoi la taille de la pile est-elle importante ??

Il faut bien une adresse de retour stockée sur la pile...

[crocodilex]

Euh.. Pardon, mais il me semble que vu que le code ne fait pas d'allocation et n'a aucune variable "à lui", en quoi la taille de la pile est-elle importante ?? A la limite il y aura du swap, mais je vois pas pourquoi on ne pourrait pas faire 500 000 appels itératifs ??? (ou bien il y a quelque chose qui m'échappe, ce qui est fort possible )

[EDIT]

Mais bon tout ceci pour dire que la première version (aux détails réglés après près) est nettement plus effiicace quand même que celle de Melem..

[/EDIT]

Lorsqu’on fait de l’allocation dynamique, la mémoire n’est certainement pas allouée dans la pile. Donc le problème n’est pas là.
Par contre les paramètres passés à une fonction sont, eux, alloués dans la pile. On y sauvegarde également l’état de certains registres ainsi que l’adresse de retour.
Donc forcément, si une fonction est appelée 500 000 fois de façon récursive, la pile aura tendance à grossir jusqu’à l’explosion.

[souviron34]

euhhh...

testez ce petit prog. et dites-moi ce qui se passe :

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
30
 
#include <stdio.h>
#include <stdlib.h>
 
 
 
static double MaFonction ( double Val )
{
  Val = Val + 1.0 ;
  fprintf ( stderr, "\r%g", Val );
  return ( MaFonction(Val) );
} 
 
 
 
/*
*********************
      main routine
 
*********************
*/
int main (int argc, char **argv)
{
  double d, d1=0.0 ;
 
 
  d=MaFonction(d1);
 
   return 0 ;
}

[EDIT]
Bon pour faire propre et correct j'aurais dû passer par adresse.. Ne faites pas la remarque ...

Mais il n'empêche que ça ne plante pas (modification "down"), et que je n'ai pas réussi à faire craquer .... (bon j'ai arrêté à 12 10^7... Mais bon ça m'étonnerait que la pile fasse autant )

[/EDIT]