Often times, while calculating odds, probabiligy, or counting the number of differnt ways a group of event can occur, you'll end up needing to use the combinatorial function which is defined as:

C(n,r) = --------

Unfortunately, the factorial function isn't very easy to calculate on a computer due to its exponential growth. After a while of trying to figure out how to do this without factorials, I came up with the following function:

int C( n, r )
int result = 0, i;
if( n / 2 < r ) r = n - r;
for( i = 1 ; i <= r ; i++ )
result = result * ( n - i ) / i;
return( result );

Which will actualy generate a result on a computer, but is rather slow due to its dependence on the division operator. Short of using a look-up table or predefined constants, is there a better way to calculate this function quickly?

Posted on 2005-03-07 16:22:08 by Sparafusile
An interesting discussion on the matter:

Please, let me know if there are problems with the code.
Posted on 2005-03-07 20:22:49 by bitRAKE
Terrific. I must have searched for the wrong thing before posting. Thanks for the link.

Posted on 2005-03-07 21:36:24 by Sparafusile