binomial coefficients

[thatwhiteguy]

I have worked out all the bugs on my program. It is compiled and it actually runs. The problem I am having is it is not giving me the right answers. I know it must be something in my equation, but after looking at it for hours, I can't seem to locate the problem. Here is my equation:

[code=c]
denominator = 1 ; // initial value
numerator = 1 ;
for (i = 1 ; i <= k+1 ; i = i+1 )
{
denominator = (i * denominator) ;

numerator = (((n - k) + i) * numerator) ;
}

return (numerator/denominator) ;[/code]

[sksriharsha]

I think you have to increment one variable inside the loop with (num/den) and return this variable after the loop.

[chroot]

That's it exactly. When you calculate the denominator separately, you get to huge numbers, and dividing them results in numerical errors (might even get an overflow with big numbers).

So to calculate ( n *( n-1) * ... * (n-k+1) ) / ( k * (k-1) * ... * 1 ), you need to always take a pair of multiplicands together:

n/k * (n-1)/(k-1) * ... * (n-k+1)/1

to avoid these errors.

To make it even better, you could check if k or n-k is the smaller number, and multiply over this number (just use k = n - k; in that case)