Revision: 27850
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at June 25, 2010 05:48 by s1m55r
Initial Code
/** * 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); }
Initial URL
Initial Description
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.
Initial Title
Calculate binomial coefficient
Initial Tags
Initial Language
C