### Lotteries revisited

No. 109

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:

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); } } 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 )$ 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:

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