StackOverflowError вычисляет факториал BigInteger?

Question

Я пытаюсь написать программу на Java для вычисления факториала большого числа.Кажется, BigInteger не может хранить такое большое число.

Ниже приведен (простой) код, который я написал.

 public static BigInteger getFactorial(BigInteger num) {
      if (num.intValue() == 0) return BigInteger.valueOf(1);

      if (num.intValue() == 1) return BigInteger.valueOf(1);

      return num.multiply(getFactorial(num.subtract(BigInteger.valueOf(1))));
  }

Максимальное число, которое вышеуказанная программа обрабатывает в 5022после этого программа выдает StackOverflowError.Есть ли другие способы справиться с этим?

Answer 1

Проблема здесь выглядит как переполнение стека из-за слишком большого количества рекурсия (5000 рекурсивных вызовов похоже на правильное количество вызовов для выброса стека вызовов Java ) и не является ограничением BigInteger.Итеративная перезапись факториальной функции должна исправить это.Например:

public static BigInteger factorial(BigInteger n) {
    BigInteger result = BigInteger.ONE;

    while (!n.equals(BigInteger.ZERO)) {
        result = result.multiply(n);
        n = n.subtract(BigInteger.ONE);
    }

    return result;
}

Надеюсь, это поможет!

Answer 2

Проблема не в BigInteger, а в том, что вы используете рекурсивный вызов метода (getFactorial()).

Answer 3

Попробуйте вместо этого итерационный алгоритм:

public static BigInteger getFactorial(int num) {
    BigInteger fact = BigInteger.valueOf(1);
    for (int i = 1; i <= num; i++)
        fact = fact.multiply(BigInteger.valueOf(i));
    return fact;
}

Answer 4

Наивные реализации факториала не работают в реальных ситуациях.

Если у вас есть серьезная необходимость, лучше всего написать функцию gamma (или функцию ln(gamma)), которая будет работать не только для целых чисел, но и для десятичных чисел. Запоминайте результаты, чтобы вам не приходилось повторять вычисления, используя WeakHashMap, и вы в деле.

Answer 5

Библиотеки Guava от Google имеют высоко оптимизированную реализацию факториала, которая выводит BigIntegers. Проверьте это . (Он делает более сбалансированные умножения и оптимизирует простые сдвиги.)