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

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

источник

2012-01-24 vinoth

Это не может быть самым большим для типов данных BigInteger. Где выбрано исключение stackoverflow? Опубликуйте более подходящий код. – JonH

Да, используйте итерационный алгоритм. BigInteger все в порядке, getFactorial просто съел все пространство стека. – harold

@harold (+1) - еще один пример того, почему я считаю, что рекурсия - это вредная техника для обучения студентов колледжа, по крайней мере, на языках без возврата хвоста. Это интеллектуальное упражнение, но в конечном счете не полезно ни для чего интересного. – CPerkins

Проблема здесь выглядит как сво stack overflow от слишком большого количества recursion (5000 рекурсивных вызовов выглядит как о правильном количестве звонков задуть Java call stack), а не ограничение 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; 
}

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

источник

2012-01-24 18:59:59 templatetypedef

Измененный код для использования статических констант 'BigInteger.ONE' и' ZERO'. – tskuzzy

В классе алгоритмов я вспомнил технику, которая использовала Push/Pop для стека, чтобы исключить исключение StackOverflow при реализации чрезвычайно глубокой рекурсивной функции Ackermann (http://en.wikipedia.org/wiki/Ackermann_function) в Java, особенно для «A (4,1)», что заняло около 28 минут для выполнения на Core2Duo T7250. –

@ ee.- Что вы описываете, это замена стека времени выполнения явным стеком. Это может быть сделано для работы, хотя сложность большинства алгоритмов, написанных таким образом, часто выше, чем рекурсивная версия. – templatetypedef

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

источник

2012-01-24 19:00:26 jtahlborn

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

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

источник

2012-01-24 19:14:22

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

источник

2012-01-24 20:50:59

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

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

источник

2012-01-24 23:16:07 duffymo

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

ответ

Смежные вопросы