Recursive function for calculating combination and factorial
I am using the following two functions to calculate factorials and combinations.
public static long Factorial(long n)
{
if (n == 0)
return 1;
else
return n * Factorial(n-1);
}
public static long combinations (long n, long k)
{
return Factorial(n)/(Factorial(k) * Factorial(n - k));
}
I am testing it using:
long test = combinations((long)21, (long)13);
It seems to work for small numbers like 5,2
. But if I try 21,13
, I get wrong answers (negative or 0).
Does anyone know what's going on here?
The maximum value long
in java is 2 ^ 63.
This will safely take you to factorial 20. However, factorial 21 approaches 2 ^ 65, so you are exceeding the maximum value that can be represented.
See this question for a discussion of what happens in java if you are performing a multiplication that causes an overflow.
source to share
This is mainly due to overflow from long
(64-bit signature). You can find BigDecimal or BigInteger for use in this case.
source to share
As other users say, it cannot contain Factorial for a long time (21). I rewrote your Factorial method with BigInteger and it seems to work, although you need to pass the BigInteger value as a parameter.
public static BigInteger Factorial(BigInteger n)
{
if (n.equals(BigInteger.ZERO))
return BigInteger.ONE;
else
return n.multiply(Factorial(n.subtract(BigInteger.ONE)));
}
Then rewrite the combination method with BigInteger:
public static BigInteger combinations (BigInteger n, BigInteger k)
{
return Factorial(n).divide(Factorial(k).multiply(Factorial(n.subtract(k))));
}
In the main method I named the combination method like this
System.out.print(combinations(new BigInteger("21"), new BigInteger("13")));
source to share