Unable to calculate number of combinations due to very large factorial

Question

I am trying to calculate the number of combinations of the number of elements in a certain array. I need the exact number of combinations to use it as number of threads to be executed in the GPU.

But the data is very big and the factorial can't be calculated for that big a number with any data type.

Is there a way to calculate the number of combinations without having to find the factorial? Or a more efficient way to do so?

It summarizes the problem:

int no_of_combinations = combination(500,2);
public static int factorial(int m)
{
        int x = 1;

        for (int i = m; i > 0; i--)
            x = x * i;

        return x;
}
public static int combination(int m, int n)
{
    int x = 0;
    x = factorial(m) / (factorial(n) * factorial(m - n));
    return x;
}

Answer 1

In this case I would start to simplify the equation. In your example you're looking for 500 choose 2, which is 500!/498!/2!. This can be easily changed to 500*499/2, which can be calculated.

In general terms if you have n choose k, you only need to calculate a "partial factorial" from n to max(k, n-k) and then divide by min(k, n-k)! due to the results being mirrored. This makes the calculation much easier.

Also in certain cases you could start dividing with the min(k, n-k)! while multiplying, but that will lead to remainders etc.