Lotteries revisited

exercise No. 108

Q:

Wrap your implementation from the section called “Loops and calculations” into a single method binomial(int n, int k). Then manually calculate smaller values such as ( 4 3 ) beforehand to define corresponding unit tests. Do not forget: ( 1 0 ) and ( 0 0 ) are valid expressions as well.

Manually calculate ( 22 2 ) and ( 22 20 ) beforehand to add more unit tests. Your implementation is likely to fail for (at least) one of these. Why does this happen? May you propose a solution? Keep in mind the idea to deal with 6 out of 90 lottery situations.

Tip

Be careful about possible arithmetic overflows.

A:

A complete implementation among with some unit tests is available at:

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 ( 22 21 ) ?

// 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:

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

  for (int i = 2; i < 22; i++) {
    factorial *= i;
    System.out.println(factorial);
  }
}
Result
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 20 ! = 2432902008176640000 < 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 ( 22 20 ) .

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

( n k ) = ( n n - k )

So instead of calculating ( 22 20 ) we take its sibling ( 22 2 ) having 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:

Code
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));
}
Result
Your chance to win when drawing 6 out of 49 is 1 : 13983816