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

Я пытаюсь написать программу 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 году, после чего программа выдает a StackOverflowError. Есть ли другие способы справиться с этим?

Ответы

Ответ 1

Проблема здесь выглядит как переполнение стека из-за слишком большого количества recursion (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;
}

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

Ответ 2

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

Ответ 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;
}

Ответ 4

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

Ответ 5

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

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