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:


n!
C(n,r) = --------
r!(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?

Spara
Posted on 2005-03-07 16:22:08 by Sparafusile
An interesting discussion on the matter:
http://www.asmcommunity.net/board/viewtopic.php?t=4978

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.

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