Inspired by two of the earlier posts, I offer this implementation and unit test case. While testing if the BigInteger class could compute and represent a factorial where n=Integer.MAX_INT, I realize this method does not return large order factorial quickly. If the user of the method needed to know the values of several large order factorials, then a better implementation would use precomputed results for all values of n and probably require database.
package com.example.math;
import java.math.BigInteger;
public class Functions {
private static long[] smallFactorialResults =
{
1,
1,
2,
6,
24,
120,
720,
5040,
40320,
362880,
3628800,
39916800,
479001600,
6227020800L,
87178291200L,
1307674368000L,
20922789888000L,
355687428096000L,
6402373705728000L,
121645100408832000L,
2432902008176640000L // n == 20
};
public static BigInteger factorial(int n)
{
final BigInteger result;
// validate argument
if ( n < 0 )
{
throw new IllegalArgumentException("cannot compute a factorial less than zero. n = " + n +
"not allowed");
}
// avoid cost of BigInteger Math if the result can fit in a long
else if ( n < smallFactorialResults.length)
{
result = BigInteger.valueOf(smallFactorialResults[n]);
}
else
{
BigInteger product = BigInteger.valueOf(smallFactorialResults[smallFactorialResults.length-1]);
for (int i = smallFactorialResults.length; i <= n; i++)
{
product = product.multiply(BigInteger.valueOf(i));
}
result = product;
}
return result;
}
}
package com.example.math;
import java.math.BigInteger;
import junit.framework.TestCase;
public class FucntionsTest extends TestCase {
public void testFactorial() {
BigInteger result = BigInteger.ONE;
try
{
result = Functions.factorial(-1);
}
catch (IllegalArgumentException ex)
{
assertTrue(true);
}
catch (Exception ex)
{
assertTrue(false);
}
assertEquals(result,BigInteger.ONE);
// simple on array look ups
assertEquals(BigInteger.valueOf(1),Functions.factorial(0));
assertEquals(BigInteger.valueOf(1),Functions.factorial(1));
assertEquals(BigInteger.valueOf(120),Functions.factorial(5));
// test boundary condition between lookups and big integer math
result = Functions.factorial(20);
assertEquals(BigInteger.valueOf(2432902008176640000L),result);
result = result.multiply(BigInteger.valueOf(21));
assertEquals(result,Functions.factorial(21));
// test more than one iteration on the loop.
result = result.multiply(BigInteger.valueOf(22));
assertEquals(result,Functions.factorial(22));
}
public void testForMaxFactorial()
{
// prove that argument n has no upper bound if typed as an integer
BigInteger result = BigInteger.ONE;
result = Functions.factorial(Integer.MAX_VALUE);
assertFalse(result.equals(BigInteger.ONE));
}
}
I'll reply to this post with the result of the testForMaxFactorial method when it completes.
