StackOverflowError computing factorial of a BigInteger?

Question

I am trying to write a Java program to calculate factorial of a large number. It seems BigInteger is not able to hold such a large number.

The below is the (straightforward) code I wrote.

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

The maximum number the above program handles in 5022, after that the program throws a StackOverflowError. Are there any other ways to handle it?

Answer 1

The problem here looks like its a stack overflow from too much recursion (5000 recursive calls looks like about the right number of calls to blow out a Java call stack) and not a limitation of BigInteger. Rewriting the factorial function iteratively should fix this. For example:

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

Hope this helps!

Answer 2

The issue isn't BigInteger, it is your use of a recursive method call (getFactorial()).

Answer 3

Try this instead, an iterative algorithm:

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