Algorithm for Calculating Binomial Coefficient

by

One of the best methods for calculating the binomial coefficient I have seen suggested is by Mark Dominus. It is much less likely to overflow with larger values for N and K than some other methods.

public static long GetBinCoeff(long N, long K)
{
   // This function gets the total number of unique combinations based upon N and K.
   // N is the total number of items.
   // K is the size of the group.
   // Total number of unique combinations = N! / ( K! (N - K)! ).
   // This function is less efficient, but is more likely to not overflow when N and K are large.
   // Taken from:  http://blog.plover.com/math/choose.html
   //
   long r = 1;
   long d;
   if (K > N) return 0;
   for (d = 1; d <= K; d++)
   {
      r *= N--;
      r /= d;
   }
   return r;
}

More Related Contents:

  1. How to check if a number is a power of 2
  2. All Possible Combinations of a list of Values
  3. Creating all possible k combinations of n items in C++
  4. Algorithm for simplifying decimal to fractions
  5. Algorithm to find which numbers from a list of size n sum to another number
  6. Getting all possible combinations from a list of numbers
  7. How can I generate truly (not pseudo) random numbers with C#?
  8. What’s the quickest way to compute log2 of an integer in C#?
  9. What is the fastest way to compute sin and cos together?
  10. Best algorithm for evaluating a mathematical expression?
  11. Finding holes in 2d point sets?
  12. Generating permutations of a set (most efficiently)
  13. C# Point in polygon
  14. Swap two variables without using a temporary variable
  15. Evaluate string with math operators [duplicate]
  16. C# Math calculator [duplicate]
  17. Make a sphere with equidistant vertices
  18. Rounding DateTime objects
  19. Built in .Net algorithm to round value to the nearest 10 interval
  20. Arbitrary-Precision Decimals in C# [duplicate]
  21. Fixed point math in C#
  22. How to round up value C# to the nearest integer?
  23. Implementing Hoey Shamos algorithm with C#
  24. Generic C# Code and the Plus Operator [duplicate]
  25. How to sort depended objects by dependency
  26. Generate all combinations for a list of strings
  27. How is a random number generated at runtime?
  28. A possible algorithm for determining whether two strings are anagrams of one another? [closed]
  29. Rotation Matrix given angle and point in X,Y,Z
  30. Why doesn’t C# use arithmetic overflow checking by default? [duplicate]

Leave a Comment