Est-ce que tu as besoin de calculer les factorielles parce que c'est un calcul intermédiaire (par exemple pour calculer des coefficients binomiaux ou des coefficients de développements en série), ou bien tu as juste besoin de calculer les factorielles pour elles-mêmes ?
Dans le premier cas, il faut procéder autrement et ne surtout pas passer par les factorielles.
Dans le second cas, tu peux utiliser des 'double' au lieu de 'int' : ça donnera une valeur approchée qui, peut-être, te satisfera ?
Je suis même surpris que tu te rendes jusqu'à 34. Mon code déconne à partir de 17. Avec des long long, je me rend jusqu'à 20. Comme l'a dit robun, ce serait mieux avec les doubles.
Ou bien passe en Python. Avec 34!
295232799039604140847618609643520000000
- Edité par PierrotLeFou 5 mars 2022 à 18:39:01
Le Tout est souvent plus grand que la somme de ses parties.
Doit être impérativement déplacée à l'intérieur de ta fonction. Actuellement ta fonction ne donne le bon résultat que la première fois où elle est appelée. Et calculer la factorielle de 17, c'est déjà un beau nombre!
comme log₂(12!)≈28.8<31<32<log₂(13!)<log₂(20!)≈61.1<63<log₂(21!)≈65.5<log₂(33!)≈122.7<127<log₂(34!)≈127.8<128<log₂(35!)≈132.9 :
un entier 32 bits (signé ou non) permet de stocker au moins 12! ;
un entier 64 bits (signé ou non) permet de stocker au moins 20! ;
en complément à 2, un entier signé de 128 bits permet de stocker au moins 33!;
en complément à 2, un entier non signé de 128 bits permet de stocker au moins 34!.
Donc soit ça déconne avant 17 (à 13) ou après (à 21) mais pas à 17 ... ou alors il y a un autre soucis (ou une plateforme exotique avec un entier sur 48 bits ⁈ ou aut'chose encore).
Un bug à 34 signifierait l'utilisation d'un entier non signé sur 128 bits (disponible en extension GNU par exemple) ou d'une plateforme où int fait 128 bits …
Sinon pour des entiers plus longs il faut utiliser … un implémentation d'entiers longs à précision arbitraire (ou une bibliothèque tierce ou une implémentation perso). Là la limite est celles des ressources à disposition. Mais bon, si tu fais un exo sur les factorielles ce ne sera pas à ta portée.
existe-t-il une fonction "pseudo" factorielle qui serait le produit des N premiers "nombres premiers", ou des nombres premiers <= N? Encore faut-il avoir cette liste de nombres premiers.
Le Tout est souvent plus grand que la somme de ses parties.
Certainement, mais au rang 14 on voit, sansfaireaucuncalcul, et sans rien supposer sur le nombre de bits des entiers, que le résultat ne s'est pas allongé alors qu'on a multiplié par un nombre supérieur à 10.
C'est suffisant pour tirer le signal d'alarme sur l'invraisemblance du résultat.
Comme le signe moins pour 17, bien sur. Mais 14 c'est avant 17 :-)
Ps m'étais planté dans les additions dans le message d'avant. 34! est bien divisible par 2^32
Certainement, mais au rang 14 on voit, sansfaireaucuncalcul, et sans rien supposer sur le nombre de bits des entiers, que le résultat ne s'est pas allongé alors qu'on a multiplié par un nombre supérieur à 10. C'est suffisant pour tirer le signal d'alarme.
Comme le signe moins pour 17.
Ps m'étais planté dans les additions dans le message d'avant. 34! est bien divisible par 2^32
- Edité par michelbillaud il y a moins de 30s
robun a écrit:
Exact : 13! ne peut pas finir par le chiffre 4 puisqu'il est divisible par 100 (au moins − il contient 2, 5, 10).
- Edité par robun il y a environ 9 heures
Si un nombre se termine par 0 si on le multiplie par un autre nombre, le résultat se terminera par 0.
PierrotLeFou a écrit:
existe-t-il une fonction "pseudo" factorielle qui serait le produit des N premiers "nombres premiers", ou des nombres premiers <= N? Encore faut-il avoir cette liste de nombres premiers.
Pendant que je faisais mes courses (du pain et du produit pour déboucher #mylife :-)) j'ai un peu généralisé le truc précédent, à savoir que 34! est divisible par 2^32. Et donc ça fait 0 si on calcule sur des entiers 32 bits.
Pour 64 bits ça sera vrai pour 66!, pour 128 bits pour 130!, pour 256bits 258! etc.
Bref pour 2^n bits, c'est vrai pour (2^n + 2)!
Idée de la preuve : dans les entiers de 1 à 2^n, il y en a 2^(n -1= qui sont multiples de 2, parmi eux 2^(n -2) qui sont multiples de 4, parmi eux 2^(n-3) multiples de 8, etc.
Donc, dans 2^n ! le facteur 2 apparait à la puissance 1 + 2 + 4 + ... 2^(n-1) = 2^n - 1
Pour avoir la puissance 2^n, il nous faut la factorielle du nombre pair qui suit 2^n, et c'est 2^n + 2.
Pour ma part, quand j'ai besoin de factorielles, sachant qu'au delà de 13 à explose les int32, je fais un tableau statique avec les valeurs précalculées. Du coup ça va vite, en O(1).
Evidemment, pour la question initiale, c'est l'exercice classique pour s'entraîner à la récursivité, on l'a tous fait. Il ne faut pas aller au delà de 13 tout simplement.
Après, dans les faits, on a rarement besoin de factorielles qui montent aussi haut.
Bien sur on va me dire que pour toute de qui est combinatoire, on peut en avoir besoin, car on a des X!/(X-N)! mais il y a des optimisations possibles pour trouver le résultat.
Un peu comme quand les matheux font (-1)^N, c'est mathématiquement élégant, mais il ne faut pas faire ça en informatique.
Tout à fait : il y a d'un côté l'écriture mathématique, utile pour la théorie, et de l'autre les calculs de l'ordinateur, qui n'utilisent surtout pas l'écriture mathématique.
Par exemple pour calculer cos(x), on pourrait croire qu'il faut calculer :
et donc calculer des factorielles. Surtout pas ! Et ce n'est pas une question d'optimisation : calculer 2!, puis 4!, puis 6! et ainsi de suite, c'est refaire sans cesse les mêmes calculs (c'est de l'optimisation à l'envers : comment faire le pire...)
Ce qu'il faut faire, c'est définir une suite \( u_n \) telle que la somme à calculer est :
soit avec une formule immédiate, ici : \( u_n(x) = (-1)^n\dfrac{x^{2n}}{(2n)!} \)
soit par récurrence, ici : (pour n >= 1) \( u_n(x) = - \, \dfrac{x^2}{2n(2n-1)} \cdot u_{n-1}(x) \) (on initialise à u_0(x) = 1 et on a calculé une fois pour toutes \( x^2 \)).
Pour les calculs pratiques, c'est bien sûr la deuxième méthode qu'il faut employer ! La boucle principale pourrait ressembler à :
deux_n += 2 ;
deux_n_moins_1 += 2 ;
u *= -x_carre / (deux_n * deux_n_moins_1) ;
somme += u ;
(J'ai écrit différemment le calcul de 2n(2n-1), là encore l'écriture mathématique n'est pas bien adaptée.)
Il faudra pas mal de termes pour avoir un dépassement de capacité : chaque u est de plus en plus petit, et diviser par 2n(2n-1) peut se faire avec des 'double' tant que n ne vaut pas dans les 10^je-ne-sais-pas-combien...
Et le cos() ne se calcule pas avec des int mais des doubles.
Disons que cela amène dans l'algo de @robun, à choisir si deux_n et deux_n_moins_un sont des int ou des double. Dans le premier cas on aura plus de calculs entiers, mais on se prend un conversion couteuse de int vers double dans la boucle, dans le second cas tout est double et c'est peut-être plus optimal.
En recherche d'emploi.
Calculer le factoriel d'un nombre à l'aide d une c
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
En recherche d'emploi.
Le Tout est souvent plus grand que la somme de ses parties.
Recueil de code C et C++ http://fvirtman.free.fr/recueil/index.html
Le Tout est souvent plus grand que la somme de ses parties.
En recherche d'emploi.