Discussion :

[sk8trasher]

Bonsoir à tous,
voilà j'ai écrit une fonction factorielle, mais le résultat affiché, n'est plus correct à partir de 32.
ça fait rager ! le programme compile, on croit qu'il est bon, mais là, on se rend compte qu'il bug!!! rrh
voici la source que j'ai écrit:

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
 
#include <stdio.h>
#include <stdlib.h>
  long factoriel (long a)
{
    if(a<=1) return 1;
    return a*factoriel(a-1);
}
int main()
{
          int nb;
 
            printf("Veuillez saisir un nombre : ");
          scanf("%d", &nb);
 
          printf("\n % d! = %ld\n\n\n\n", nb, factoriel(nb));
 
 
 
          return 0;
}

Je vous remercie de l'aide que vous pourrez m'apporter.

[Neckara]

Code :

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

1
2
3
4
5
6
 
 long factoriel (long a)
{
    if(a<=1) return 1;
    return a*factoriel(a-1);
}

Une fonction récursive n'est pas très adaptée à ce genre de problème car plus a est grand, plus tu appelles ta fonction et plus tu empiles et dépiles sur la pile d'appel.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
 unsigned long factoriel (unsigned int a) //on aura pas de valeur négative, unsigned permet donc de travailler avec des chiffres 2x plus grands.
//tu lis la valeur de a avec un %d donc tu lis un int (donc autant metre un int en paramètre qu'un long), tu devrais plutôt utiliser un %u pour lire un unsigned int.
{
      unsigned long resultat = 1;
      while(a > 1)
      {
                resultat *= a;
                a--;
       }
        return resultat;
}
//ceci me semble plus rapide et plus léger.

Tu peux même rajouter des conditions :

Code :

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

1
2
3
 
if(sizeof(long) == 4 && a > 12)
       return 0; //signifie que a est trop grand pour pouvoir calculer le factoriel

Il est possible de le faire avec le compilateur avec des #if sizeof() il me semble.

En effet, il ne faut pas oublier qu'un entier peut aller jusqu'à (2^8)^(taille)/2 - 1.
Un entier non-signé peut aller jusqu'à : (2^8)^(taille) - 1

Or la fonction factorielle croît très vite, 32! = 2.63x10^35 Il est fort probable que tu fasse un overflow^^
(unsigned long int étant code sur 4 ou 8 octets il me semble).

Un entier, s'il est codé sur 8 octets va jusqu'à 1,88x10^19
S'il est codé sur 16 octet il va jusqu'à 3.40x10^38

[diogene]

Il est possible de le faire avec le compilateur avec des #if sizeof() il me semble.

Non, pas en standard. Voir la discussion récente Directives du préprocesseur

[sk8trasher]

Ok, du coup, si je comprend bien, le type de mes variables n'était pas correct, et les résultats obtenus étant très vite élevés, le compilateur ne suit pas.
Merci

[Trademark]

Non ce n'est pas ça. Déjà, ça n'a rien à voir avec le compilateur, c'est à l'exécution que ça foire. En fait, un entier (int) est souvent codé sur 4 octets, ce qui permet de représenter un nombre allant jusqu'à environ 2 milliards, ou plus précisément 2^31. Un int est représenté sur 32 bits, dont 1 bit pour le signe, voilà pourquoi 2^31.

La factorielle de 13 = 6 227 020 800, ce qui dépasse 2^31. Ce qui se passe alors, c'est que ton nombre se retrouve tronqué par la gauche et donc des bits représentitfs sont perdus. Par exemple si tu as 15 en binaire c'est :

1111

Si tu fais 15 + 1 ça fait alors :

10000

Seulement c'est sur 5 bits, dans une variable de 4 bits, tu n'as plus que les 4 zéros ce qui donne un résultat incorrect. C'est le même phénomène qui se produit dans ton cas.

Tu peux utiliser des unsigned long pour aller jusqu'à 2^64. Et si tu veux monter plus haut il faudra que tu crées toi même ton type entier en utilisant des tableaux et en faisant les calculs nécessaires.

J'ajouterai que ta fonction récursive ne posais pas de problème le nombre de récursion seront faibles. C'est donc un moyen élégant de coder cette solution. Par contre la solution de Neckara convient et devient nécessaire pour les récursions plus profonde et lorsqu'on veut économiser la mémoire. Néanmoins, spécifiquement pour cette fonction, qui est une fonction récursive terminale, le compilateur optimise lui-même cette fonction et la dérécursifie tout seul.

[sk8trasher]

Ok merci pour cette réponse très claire. Au niveau de la formation que je suit, je n'ai encore jamais vu comment on créer un type.
Du coup pour mon devoir, je laisserai un commentaire qui explique pour ça veut plus marcher à partir de 32
Merci

[denispir]

J'ajouterai que ta fonction récursive ne posais pas de problème le nombre de récursion seront faibles. C'est donc un moyen élégant de coder cette solution. Par contre la solution de Neckara convient et devient nécessaire pour les récursions plus profonde et lorsqu'on veut économiser la mémoire. Néanmoins, spécifiquement pour cette fonction, qui est une fonction récursive terminale, le compilateur optimise lui-même cette fonction et la dérécursifie tout seul.

Les compilos C font ça (tail call optimisation) ? Ou seulement certains, pour le fun et la vitesse ? C'est dans le standard ?

Denis