3
$\begingroup$

I am reading Algorithm Design Manual by Skiena, which says in Chapter 8, Section 8.1.4 when talking about the calculation of binomial coefficients:

Intermediate calculations can easily cause arithmetic overflow, even when the final coefficient fits comfortably within an integer.

I can’t think of a reason why. Shouldn’t whatever calculation is done in between always be less than the final result?

$\endgroup$
  • 3
    $\begingroup$ Stupid simple example: f(x) = (x + 1) - 1. The intermediate result is larger than the end result. $\endgroup$ – apnorton Mar 25 '15 at 20:57
11
$\begingroup$

The problem with binomial coefficients is that they are a quotient of factorials, which may be rather large and in particular much larger than the final binomial coefficent:

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

For example, $\binom{10}{5}=252$ but $10!=3628800$ (the numerator). In another example $\binom{100}{5}=75287520$ and thus can be represented as a regular integer, while $100! \approx 10^{158}$ cannot be represented as an integer.

Thus, when calculating the binomial coefficient, it’s usually unwise to just calculate $n!$ and $k!(n-k)!$ and divide the two, because your computer may not be able to handle $n!$. Instead, you need to consider ways that do not contain large numbers as intermediate results such as:

$$ \binom{n}{k} = \prod\limits_{i=1}^k \frac{n+1-i}{i}$$

Here, each factor is a comparibly small integer and no intermediate result is larger than the final result.

Even then, binomial coefficients may become very large easily (and even be beyond the limits of floats) and may only be intermediate results themselves. You may thus need to resort to calculating everything in the logarithmic domain and making use of an approximation of the factorial such as Stirling’s. Most math libraries provide a loggamma function for such purposes, which returns $\log(\Gamma(n))= \log((n-1)!)$. (On the other hand, many math libraries also provide a reasonable implementation of binomial coefficients.)

| cite | improve this answer | |
$\endgroup$
7
$\begingroup$

Intermediate results may overflow even if the final result doesn't. There are ways one can re-arrange an equation so that this doesn't happen but it's up to the programmer (maybe an optimizing compiler that's also a theorem solver can do it too - but I've never seen one) and the CPU won't re-order a sequence of arithmetic instructions on its own.

Instead of trying to prove it in theory I'll merely provide a trivial example of at least one instance of it happening:

Assume an 8 bit machine for simplicity:

int8 a = 10
int8 b = 30
int8 c

c = (a * b) / 2

The end result is 150. Which fits in an 8 bit register. But the intermediate result, (a * b) is 30 x 10 which is 300 which doesn't fit in an 8 bit register and thus overflows.

Due to the overflow, if one were to run the above calculation on an 8 bit machine, the result would be a surprising 22 instead of 150 (300 mod 256 is 44 and 44/2 = 22).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy