usando - factorial java math

Cuando calculo el factorial de 100(100!) Con Java usando enteros, obtengo 0

Question

Al hacer esto:

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

Esto es claramente porque el resultado es demasiado grande para un entero, pero estoy acostumbrado a obtener números negativos grandes para el desbordamiento, y no a 0.

¡Gracias por adelantado!

Cuando cambio a esto:

int x = 100;
int result = 1;

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

Entiendo esto

Answer 1

( Aquí se encuentra, se adaptó ligeramente para adaptarse a la pregunta)

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);
}

Answer 2

Buen problema: la respuesta es: Factorial de 33 (debido a valores negativos) es -2147483648 que es 0x80000000 , o 0xFFFFFFFF80000000 si toma 64bits. Multiplicar por 34 (el siguiente miembro) dará un valor largo de 0xFFFFFFE600000000 , que al 0xFFFFFFE600000000 a int le dará 0x00000000 .

Obviamente desde ese punto en adelante, permanecerás con 0.

Answer 3

Hay 50 números pares entre 1 y 100 inclusive. Esto significa que el factorial es un múltiplo de 2 al menos 50 veces, en otras palabras, como un número binario, los últimos 50 bits serán 0. (En realidad, es más, ya que incluso el segundo número par es un múltiplo 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;
}

huellas dactilares

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

Esto significa que un entero de 97 bits sería 0 para los bits de hecho más bajos (100)

De hecho, el número de potencias de dos está muy cerca de n de hecho (n). De hecho (10000) hay 9995 poderes de dos. Esto se debe a que es aproximadamente la suma de n veces los poderes de 1/2 dando un total cercano a n . es decir, cada segundo número es n / 2 y cada 4 tiene una potencia adicional de 2 (+ n / 4) y cada 8 tiene una potencia adicional (+ n / 8) etc. se acerca a n como una suma.

Answer 4

Los números negativos grandes son valores que se desbordaron en ciertos rangos; factorial(100) tiene más de 32 ceros binarios en el extremo, por lo que convertirlo en un número entero produce cero.

Answer 5

Para echar un vistazo a la causa, podríamos observar la factorización prima del factorial.

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 * ...

El exponente para el 2 es el número de ceros finales en la vista de base 2, ya que todos los otros factores son impares y, por lo tanto, contribuyen con un 1 en el último dígito binario del producto.

Un esquema similar también funciona para otros números primos, por lo que podemos calcular fácilmente la factorización 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

Entonces, si nuestra computadora almacenara los números en la base 3, y tuviera 48-trit-numbers, fac(100) sería 0 (como fac(99) , también, pero fac(98) no :-)

Answer 6

Solución simple usando recursion y BigIntegers:

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

Salida:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Answer 7

es seguro que se trata de un desbordamiento, puedes intentar el doble, un entero de 64 bits probablemente sea demasiado pequeño