Class members and methods

This actually wraps Equation 1, “Calculating binomials by cancelling common factors.” into a method public static long binomial(int n, int k).

What happens when calculating $\left(\begin{array}{c}\mathrm{22}\\ \mathrm{21}\end{array}\right)$ ?

// Numerator product n (n - 1) ... (n - k + 1)
long numerator = 1;
for (int i = n - k + 1; i <= n; i++) {
  numerator *= i;
}

In this case our numerator variable of type long will be set to a value 22! (factorial). Consider a simple demo code snippet among with its result:

public static void main(String[] args) {
  long factorial = 1;

  for (int i = 2; i < 22; i++) {
    factorial *= i;
    System.out.println(factorial);
  }
}

2: 2
3: 6
4: 24
5: 120
6: 720
7: 5040
8: 40320
9: 362880
10: 3628800
11: 39916800
12: 479001600
13: 6227020800
14: 87178291200
15: 1307674368000
16: 20922789888000
17: 355687428096000
18: 6402373705728000
19: 121645100408832000
20: 2432902008176640000
21: -4249290049419214848

Largest long value:9223372036854775807

So 21! already yields a negative value. Actually $\mathrm{20}!=\mathrm{2432902008176640000}<\mathrm{9223372036854775807}$ still holds. The subsequent multiplication by 21 however results in an arithmetic overflow.

This does not show up as an error since exactly the same (mis)calculation happens for the denominator. Thus their quotient by coincidence returns a correct value of 1. This however is no longer true when examining $\left(\begin{array}{c}\mathrm{22}\\ \mathrm{20}\end{array}\right)$.

We may still get correct results in many situations including the given example. If k gets too large we may use:

So instead of calculating $\left(\begin{array}{c}\mathrm{22}\\ \mathrm{20}\end{array}\right)$ we take its sibling $\left(\begin{array}{c}\mathrm{22}\\ 2\end{array}\right)$ of identical value:

public static long binomial(int n, int k) {

  // Trying to avoid arithmetic overflow using:
  //             n        n
  //           (   ) =  (   )
  //             k       n-k
  //
  if (n - k < k) {
    k = n - k;
  }

  // Numerator product n (n - 1) ... (n - k + 1)
  long numerator = 1;
 ...

Finally our lottery code from the section called “Loops and calculations” gets a little bit simplified:

final int
  totalNumberCount = 49,
  drawnNumberCount = 6;

System.out.println(
  "Your chance to win when drawing " + drawnNumberCount +
  " out of " + totalNumberCount +
  " is 1 : " + Binomial.binomial(totalNumberCount, drawnNumberCount));
}

Your chance to win when drawing 6 out of 49 is 1 : 13983816