En calculant le factoriel de 100 (100!) avec Java utilisant des entiers j'obtiens 0

en faisant ceci:

int x = 100;
int result = 1;
for (int i = 1; i < (x + 1); i++) {
    result = (result * i);
}
System.out.println(result);

c'est clairement parce que le résultat est trop grand pour un entier, mais je suis utilisé pour obtenir de grands nombres négatifs pour le débordement, et pas 0.

Merci d'avance!


quand je passe à ceci:

int x = 100;
int result = 1;

for (int i = 1; i < (x + 1); i++) {
    result = (result * i);
    System.out.println(result);
}

je reçois ce .

14
demandé sur MC Emperor 2011-03-15 23:36:56

8 réponses

Grand nombres négatifs sont des valeurs qui débordait dans certaines gammes; factorial(100) a plus de 32 zéros binaires sur la fin, de sorte que la conversion d'un nombre entier en produit de zéro.

21
répondu Jeremiah Willcock 2011-03-15 20:41:19

il y a 50 nombres pair entre 1 et 100 inclusivement. Cela signifie que le factoriel est un multiple de 2 au moins 50 fois, en d'autres termes comme un nombre binaire les 50 derniers bits seront 0. (En fait, il est plus que même deuxième nombre pair est un multiple de 2*2 etc)

public static void main(String... args) {
    BigInteger fact = fact(100);
    System.out.println("fact(100) = " + fact);
    System.out.println("fact(100).longValue() = " + fact.longValue());
    System.out.println("fact(100).intValue() = " + fact.intValue());
    int powerOfTwoCount = 0;
    BigInteger two = BigInteger.valueOf(2);
    while (fact.compareTo(BigInteger.ZERO) > 0 && fact.mod(two).equals(BigInteger.ZERO)) {
        powerOfTwoCount++;
        fact = fact.divide(two);
    }
    System.out.println("fact(100) powers of two = " + powerOfTwoCount);
}

private static BigInteger fact(long n) {
    BigInteger result = BigInteger.ONE;
    for (long i = 2; i <= n; i++)
        result = result.multiply(BigInteger.valueOf(i));
    return result;
}

imprime

fact(100) = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
fact(100).longValue() = 0
fact(100).intValue() = 0
fact(100) powers of two = 97

cela signifie qu'un entier de 97 bits serait 0 pour les bits de fait les plus bas(100)

En fait, le nombre de pouvoirs de deux est très proche de n de fait(n). En fait (10000) il y a 9995 pouvoirs de deux. C'est parce que son est approximativement la somme de N fois des puissances de 1/2 donnant un total proche de n . c'est-à-dire que chaque deuxième nombre est pair n/2 et chaque 4ème a une puissance supplémentaire de 2 (+n/4) et chaque 8ème a une puissance supplémentaire (+n/8) etc approche n comme une somme.

22
répondu Peter Lawrey 2011-03-15 21:40:44

pour voir la cause, on a pu observer la première factorisation du factoriel.

fac( 1) = 1             = 2^0
fac( 2) = 2             = 2^1
fac( 3) = 2 * 3         = 2^1 * 3
fac( 4) = 2 * 2 * 2 * 3 = 2^3 * 3
fac( 5) =  ...          = 2^3 * 3 * 5
fac( 6) = ...           = 2^4 * 3^2 * 5
fac( 7) = ...           = 2^4 * ...
fac( 8) = ...           = 2^7 * ...
fac( 9) = ...           = 2^7 * ...
fac(10) = ...           = 2^8 * ...
fac(11) = ...           = 2^8 * ...
...
fac(29) = ...           = 2^25 * ...
fac(30) = ...           = 2^26 * ...
fac(31) = ...           = 2^26 * ...
fac(32) = ...           = 2^31 * ...
fac(33) = ...           = 2^31 * ...
fac(34) = ...           = 2^32 * ...  <===
fac(35) = ...           = 2^32 * ...
fac(36) = ...           = 2^34 * ...
...
fac(95) = ...           = 2^88 * ...
fac(96) = ...           = 2^93 * ...
fac(97) = ...           = 2^93 * ...
fac(98) = ...           = 2^94 * ...
fac(99) = ...           = 2^94 * ...
fac(100)= ...           = 2^96 * ...

l'exposant pour le 2 est le nombre de zéros traînants dans la vue de base-2, comme tous les autres facteurs sont impairs, et contribuent ainsi un 1 dans le dernier chiffre binaire au produit.

un schéma similaire fonctionne pour d'autres nombres premiers, aussi, de sorte que nous pouvons facilement calculer la factorisation de fac(100) :

fac(100) = 2^96 * 3^48 * 5^24 * 7^16 * 11^9 * 13^7 * 17^5 * 19^5 * 23^4 *
           29^3 * 31^2 * 37^2 * 41^2 * 43^2 * 47^2 *
           53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97

donc, si notre ordinateur stockait les nombres dans la base 3, et avait 48-trit-nombres, fac(100) serait 0 (comme fac(99) , aussi, mais fac(98) ne serait pas: -)

8
répondu Paŭlo Ebermann 2011-03-15 21:35:10

problème de Nice - réponse est: Le facteur de 33 (dû à des valeurs négatives) est -2147483648 qui est 0x80000000 , ou 0xFFFFFFFF80000000 si vous prenez 64bits. En multipliant par 34 (le membre suivant), on obtient une valeur longue de 0xFFFFFFE600000000 , qui donne 0x00000000 en casting to int .

évidemment à partir de ce point vous resterez avec 0.

6
répondu RonK 2011-03-15 20:47:40

la solution la plus Simple en utilisant la récursivité et BigIntegers:

    public static BigInteger factorial(int num){
    if (num<=1)
        return BigInteger.ONE;
    else
        return factorial(num-1).multiply(BigInteger.valueOf(num));
    }

sortie:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
2
répondu Jack Ca 2015-11-22 02:20:43

(trouvé ici , adapté légèrement pour répondre à la question)

public static void main(String[] args) {

    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 1; i <= 100; i++)
        fact = fact.multiply(BigInteger.valueOf(i));
    System.out.println(fact);
}
0
répondu BbJug 2017-05-23 10:30:43

Classe BigInteger en Java. La classe BigInteger est utilisée pour l'opération mathématique qui implique de très grands Calculs entiers qui sont en dehors de la limite de tous les types de données primitives disponibles.

pour calculer le très grand nombre, nous pouvons utiliser BigInteger

comme, si nous voulons calculer le factoriel de 45, answer = 119622220865480194561963161495657715064383733760000000000

 static void extraLongFactorials(int n) {
       BigInteger fact = BigInteger.ONE;
        for(int i=2; i<=n; i++){
            fact = fact.multiply(BigInteger.valueOf(i));
        }
        System.out.println(fact);
    }

les principales méthodes de BigInteger est BigInteger.L'UN, BigInteger.Zéro, BigInteger.Dix, BigInteger.ValueOf()

0
répondu Maulik Sakhida 2018-10-03 07:50:08

c'est un dépassement de capacité pour vous, vous pouvez essayer de double, 64 bits entier long sont probablement trop petite

-1
répondu Julien Vermillard 2011-03-15 20:45:12