Quand je calcule une grande factorielle, pourquoi ai-je un nombre négatif?

Question

Donc, procédure simple, calculez un nombre factoriel. Le code est le suivant.

int calcFactorial(int num)
{
    int total = 1;

    if (num == 0)
    {
        return 0;
    }

    for (num; num > 0; num--)
    {
        total *= num;
    }

    return total;
}

Maintenant, cela fonctionne bien et dandy (il existe certainement des solutions plus rapides et plus élégantes, mais cela fonctionne pour moi) pour la plupart des numéros. Cependant, lors de la saisie de nombres plus importants, tels que 250, il faut carrément craquer. Maintenant, le premier couple factoriel " bits " Pour 250, consultez {250, 62250, 15126750, 15438000, 3813186000} comme référence.

Mon code crache {250, 62250, 15126750, 15438000, -481781296 }, ce qui est évidemment désactivé. Mon premier soupçon était peut-être que j'avais dépassé la limite d'un entier de 32 bits, mais étant donné que 2 ^ 32 est 4294967296, je ne le pense pas. La seule chose à laquelle je peux penser est peut-être que cela dépasse la limite signée 32 bits, mais ne devrait-il pas être en mesure de penser à ce genre de chose? Si le fait de signer est le problème, je peux résoudre ce problème en rendant l’entier non signé mais ce ne serait qu’une solution temporaire, car la prochaine itération donne 938043756000, ce qui est bien au-dessus de la limite de 4294967296.

Alors, mon problème est-il la limite signée? Si tel est le cas, que puis-je faire pour calculer de grands nombres (bien que j’aie une classe "LargeInteger" que j’ai faite il ya quelque temps et qui convienne peut-être!) Sans rencontrer ce problème à nouveau?

Answer 1

2 ^ 32 ne vous donne pas la limite pour les entiers signés.

La limite du nombre entier signé est en réalité 2147483647 . (Si vous développez sous Windows en utilisant les outils MS, les autres suites d’outils / plates-formes auront leurs propres limites qui sont probablement similaires.)

Vous aurez besoin d'une bibliothèque de grands nombres C ++ comme celle-ci .

Answer 2

En plus des autres commentaires, je voudrais signaler deux graves problèmes dans votre code.

• Vous n'avez aucune garde contre les nombres négatifs.
• La factorielle de zéro est un, pas zéro.

Answer 3

Oui, vous atteignez la limite. Un int en C ++ est, par définition, signé. Et non, C ++ ne pense pas, jamais. Si vous lui dites de faire quelque chose, il le fera, même si c'est manifestement faux.

Pensez à utiliser une bibliothèque à grand nombre. Ils sont nombreux pour C ++.

Answer 4

Si vous ne spécifiez pas signé ou non signé, la valeur par défaut est signée. Vous pouvez modifier cela en utilisant un commutateur de ligne de commande sur votre compilateur.

N'oubliez pas que C (ou C ++) est un langage de très bas niveau et fait précisément ce que vous lui demandez de faire . Si vous lui dites de stocker cette valeur dans un entier signé, c'est ce qu'il va faire. Vous devez, en tant que programmeur, savoir quand un problème se pose. Ce n'est pas le travail de la langue.

Answer 5

Ma calculatrice Windows ( Démarrer-Exécuter-Calc ) me dit que

hex (3813186000) =         E34899D0
hex (-481781296) = FFFFFFFFE34899D0

Alors oui, la cause est la limite signée. Puisque les factorielles ne peuvent par définition être que positives et ne peuvent être calculées que pour des nombres positifs, l'argument et la valeur de retour doivent être des nombres non signés. (Je sais que tout le monde utilise int i = 0 dans les boucles for, tout comme moi. Mais cela dit, nous devrions toujours utiliser des variables non signées si la valeur ne peut pas être négative, c'est une bonne pratique IMO).

Le problème général des factorielles est qu’elles peuvent facilement générer de très grands nombres. Vous pouvez utiliser un float, sacrifiant ainsi la précision mais évitant le problème de dépassement d'entier.

Oh, attendez, selon ce que j'ai écrit ci-dessus, vous devriez en faire un float non signé ;-)

Answer 6

Vous avez un problème de débordement. Les factorielles peuvent facilement dépasser les limites des nombres entiers. Vous pouvez modifier votre fonction pour renvoyer des doubles, mais cela ne vous fera que gagner un peu plus de place. Dans les applications, il est souvent nécessaire de multiplier par plusieurs temps factoriels des nombres très petits pour lesquels le résultat final tient dans un double mais pas les étapes intermédiaires. Voici un article qui explique comment gérer cette situation: http://www.johndcook.com/blog/2008/04/24/how-to-calculate-binomial-probabilities/

Answer 7

Si je me souviens bien:

unsigned short int = max 65535

unsigned int = max 4294967295

unsigned long = max 4294967295

unsigned long long (Int64) = max 18446744073709551615

Source modifiée:

Valeurs Int / Long Max

Variable du compilateur moderne