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

[Trademark]

Attention ça ne marche plus avant 32! Essaye avec un unsigned long et regarde à partir de quand tu as des valeurs qui ne correspondent plus. Compare avec des valeurs sûres sur internet

[sk8trasher]

Oh oui, en effet ça déconne à partir de 13. 13! donne un nombre au alentour de 6milliards. J'ai essayé en changeant le type de a ((unsigned int a)int en long). Mais le nombre doit encore être trop élevé.

[Trademark]

Normalement un unsigned long long est sur 8 octets, soit 64 bits et par conséquent pouvant représenter jusqu'à 2⁶⁴ valeurs. C'est ~1.844674407×10¹⁹. La factorielle de 21! = 5.109094217×10¹⁹. Donc par conséquent, tu peux aller jusque 20.

Sur certains systèmes les unsigned long long ne font pas tous la même taille. Tu peux vérifier que le tiens fait bien 8 octets en faisant :

Code :

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

printf("%zu\n", sizeof(unsigned long long));

[diogene]

Normalement un unsigned long est sur 8 octets, soit 64 bits ....

La norme dit qu'il fait au moins 32 bits. Pour être sûr d'avoir 64 bits, il faut un (unsigned) long long

Lorsque l'opérande de sizeof est un type, celui-ci doit être mis entre parenthèses : sizeof (unsigned long)

[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

[denispir]

Oh oui, en effet ça déconne à partir de 13. 13! donne un nombre au alentour de 6milliards. J'ai essayé en changeant le type de a ((unsigned int a)int en long). Mais le nombre doit encore être trop élevé.

Ca fait combien 2^32 (-1) ?
Astuce : 2^10, c'est 1k. (donc 2^30, c'est 1G)

Denis

[Neckara]

Je doute que tu puisse vraiment utiliser les types standard pour une fonction factorielle.

Certains nombre sont stocké sur 4096 octets avec lesquels ils font des multiplications (clé RSA par exemple), je pense donc qu'il doit exister des bibliothèques permettant d'utiliser des entiers de très grande taille, tu devrais plutôt aller regarder de ce côté là.

Dans mon post ci-plus haut, j'avais fait des calculs, si je ne me suis pas trompé, il te faut un entier non signé codé sur 16 octets pour pouvoir calculer 32!