Posted By

s1m55r on 06/25/10

Tagged

Versions (?)

Last Edited at 06/25/10 05:48am

Statistics

Viewed 239 times

Favorited by 0 user(s)

Related snippets

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.

Highlighted TextExpand

/**
 * 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 <sameervijaykar@gmail.com>
 *
 * 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);
}

Report this snippet Tweet

Comments

Subscribe to comments

Comment:

You need to login to post a comment.