При вычислении факториала 100 (100!) В Java с использованием целых чисел я получаю 0

Question

При этом:

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

Это очевидно, потому что результат слишком велик для целого числа, но я привык получать большие отрицательные числа для переполнения, а не 0.

Заранее спасибо!

---

Когда я переключаюсь на это:

int x = 100;
int result = 1;

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

Я получаю это .

Answer 1

Есть 50 четных чисел от 1 до 100 включительно. Это означает, что факториал кратен 2, по крайней мере, 50 раз, другими словами, в качестве двоичного числа последние 50 бит будут равны 0. (На самом деле это больше, так как четное второе четное число кратно 2 * 2 и т. Д.)

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

печать

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

Это означает, что 97-разрядное целое число будет 0 для младших битов факта (100)

Фактически, число степеней двух очень близко к n для факта (n). Для факта (10000) существует 9995 степеней двух. Это потому, что это приблизительно сумма n-кратных степеней 1/2, что дает общее значение, близкое к n. то есть каждое второе число является четным n / 2, и каждое четвертое имеет дополнительную степень 2 (+ n / 4), а каждое восьмое имеет дополнительную степень (+ n / 8) и т. д., приближается к n как сумма.

Answer 2

Большие отрицательные числа - это значения, которые вышли за пределы определенных диапазонов; factorial(100) имеет более 32 двоичных нулей на конце, поэтому преобразование его в целое число приводит к нулю.

Answer 3

Чтобы взглянуть на причину, мы могли бы наблюдать первичную факторизацию факториала.

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

Показатель степени для 2 - это число конечных нулей в представлении base-2, так как все остальные факторы нечетны и, таким образом, дают 1 в последней двоичной цифре для продукта.

Аналогичная схема работает и для других простых чисел, поэтому мы можем легко вычислить факторизацию 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

Таким образом, если бы наш компьютер хранил числа в базе 3 и имел 48 тритовых чисел, fac(100) был бы равен 0 (как и fac(99), но fac(98) не будет: -)

Answer 4

Хорошая проблема - ответ: Факториал 33 (из-за отрицательных значений) равен -2147483648, что составляет 0x80000000, или 0xFFFFFFFF80000000, если брать 64 бита.Умножение на 34 (следующий член) даст длинное значение 0xFFFFFFE600000000, которое при приведении к int даст вам 0x00000000.

Очевидно, что с этого момента вы останетесь с 0.

Answer 5

Простое решение с использованием рекурсии и BigIntegers:

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

Вывод:

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Answer 6

Класс BigInteger на Java. Класс BigInteger используется для математической операции, которая включает в себя очень большие целочисленные вычисления, выходящие за пределы всех доступных примитивных типов данных.

Для вычисления очень большого числа мы можем использовать BigInteger

Например, если мы хотим вычислить факториал 45, ответ = 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);
    }

Основными методами BigInteger являются BigInteger.ONE, BigInteger.ZERO, BigInteger.TEN, BigInteger.ValueOf ()

Answer 7

(найдено здесь , адаптировано слегка под вопрос)

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 8

наверняка переполнение, вы можете попробовать двойное, 64-битное целое число, вероятно, слишком мало