Holy cow, I wrote a book!
When you ask a mathematician to come up with a formula to solve
you will get something that looks pretty,
but that doesn't mean that it lends itself well to computation.
For example, consider the binomial coefficient,
and in more modern notation as
( nk ).
If you ask a mathematician for a formula for the binomial coefficient,
you will get the elegant reply
(That took forever to format.
I will use the traditional notation from now on purely for
This is a very beautiful formula,
but it's horrible for actual computation
because the factorials will be very expensive
and are likely to overflow your integer data type even at
low values of n.
(So you may as well just use a lookup table.)
And the k! in the denominator exactly cancels the
first k factors in
so most of your work in multiplying the numbers together
is just going to be undone by the division.
For computation, you're much better off using the recurrence
C(n, k) =
C(n − 1, k − 1) × n ∕ k.
This is the recurrence you learned in high school when you had
to calculate binomial coefficients by hand:
You start with
1 · xⁿ
to get the next coefficient,
you multiply by the exponent on the x
and divide by the current position (starting at 1),
then decrement the exponent.
For example, let's calculate the binomial coefficients
(Am I the only person who calculated binomial coefficients by hand?)
Notice that the calculations in the second half are the exact
inverse of the calculations of the first half,
so you only have to do the computations halfway,
and then you can just mirror the rest.
This is just another way of seeing that
C(n, k) = C(n, n − k).
This technique lets you evaluate
C(50, 7) = 99884400 without overflowing a 32-bit integer.
Often people will ask for an efficient way of calculating
when in fact they don't really need factorials
(which is a good thing, because that would require a
they are really just trying to evaluate a formula that
happens to be expressed mathematically with factorials
(because factorials are pretty).
Another place pretty formulas prove unsuitable for computation
is in Taylor series.
The denominator of a Taylor series is typically a factorial,
and the numerator can get quite large, too.
exp(x) = Σ xⁿ ∕ n!.
Instead of calculating the power and factorial at each term,
use the recurrence
In compiler-terms, you're strength-reducing the loop.
Of course, another problem
is that you are adding large numbers first,
and then adding smaller numbers later.
From a numerical analysis point of view,
you should add the smaller numbers first
so that they can retain significance longer.
As an example,
consider that you have to add the following numbers:
and ten 0.1's,
and suppose your floating point format is good to only
three significant digits.
If you added them largest to smallest, you would get this:
Your final total will be 999.
But if you added the smaller numbers first, then you would get
By adding the small numbers first, you gave them a chance
to accumulate to something meaningful before the big number
came along and swamped them.
Remember, the way a formula is written on paper is not necessarily
the best way of computing it.
(And if the formula was written by a mathematician, it is almost