## Posted By

s1m55r on 06/25/10

# Calculate binomial coefficient

/ Published in: C

Program to calculate large binomial coefficients efficiently. As long as the value fits into an unsigned long long int, the program should find it in a relatively short amount of time.

`/** * Program to calculate large binomial coefficients  * efficiently. As long as the value fits into an * unsigned long long int, the program should find * it in a relatively short amount of time. * * Author: Sameer Vijaykar <[email protected]> * * References: * http://blog.plover.com/math/choose.html * http://en.wikipedia.org/wiki/Binary_GCD_algorithm * */ #include<stdio.h> typedef unsigned long long int LL; /** * Sourced from Wikipedia  * http://en.wikipedia.org/wiki/Binary_GCD_algorithm#Implementation_in_C */LL gcd(LL u, LL v){  int shift;   /* GCD(0,x) := x */  if (u == 0 || v == 0)    return u | v;   /* Let shift := lg K, where K is the greatest power of 2     dividing both u and v. */  for (shift = 0; ((u | v) & 1) == 0; ++shift) {    u >>= 1;    v >>= 1;  }   while ((u & 1) == 0)    u >>= 1;   /* From here on, u is always odd. */  do {    while ((v & 1) == 0)  /* Loop X */      v >>= 1;     /* Now u and v are both odd, so diff(u, v) is even.       Let u = min(u, v), v = diff(u, v)/2. */    if (u < v) {      v -= u;    } else {      LL diff = u - v;      u = v;      v = diff;    }    v >>= 1;  } while (v != 0);   return u << shift;} int main(){  int n, k, g, i, i1;  LL f;   printf("Enter integers n and k: ");  scanf("%d", &n);  scanf("%d", &k);   // Check for trivial cases  if ((n == k) || (n == 1) || (k == 1))    {      printf("nCk : 1\n");      return 0;    }   /* Beyond this check, everything going into the     loop will at least be 1 */   f = 1;   /* Pick the smaller denominator */  k = (k < (n-k) ? k : (n-k));   for (i = 1; i <= k; i++)    {      // Compute f = f * (n/i)       if (n % i == 0)	{	  f *= (n/i);	}      else if (f % i == 0)	{	  f = (f/i) * n;	}      else	{	  g = gcd(f, i);	  f /= g;	  i1 = i/g;	  if (n % i1 == 0)	    {	      f *= (n/i1);	    }	  else	    {	      f = (f*n) / i1;	    }	}       n--;    }   printf("nCk : %lld\n", f);}`