7
$\begingroup$

I need to calculate all the numbers in a certain row of Pascal's triangle. Obviously, this is easy to do with combinatorics. However, what do you do when you need to estimate all the numbers in, say, the 100000th row of Pascal's triangle?

Is there any way to estimate the number so that the costly multiplications and divisions of binomials can be avoided? I'm already estimating factorials with Stirling's formula, but it still takes a number of seconds to calculate only one number - and I need about 100000/2 (since a row is symmetric).

$\endgroup$
6
  • $\begingroup$ "Number of seconds"? With Stirling's formula you can estimate one Binomial coefficient with less then 20 arithmetic operations (some logs, multiplications, additions, and a final exponentiation). Your computer ought to be able to handle up to several million of these a second! Ahh... you're using logarithms, right? $\endgroup$
    – whuber
    Oct 14, 2010 at 14:58
  • $\begingroup$ A very rough estimate: every entry in the $n$th row will be less than $2^n$. $\endgroup$
    – Rasmus
    Oct 14, 2010 at 15:01
  • $\begingroup$ Well, considering that the answer to Stirling's formula is several 100-1000s digits long, it takes a few milliseconds to calculate. That's not the bottleneck though, it is the multiplication and division of such large numbers that are taking really long. Maybe there's some way to speed that up in the code? $\endgroup$
    – Herman
    Oct 14, 2010 at 15:06
  • $\begingroup$ @Rasmus: That is indeed very rough. Since we know the row adds up to $2^n$, can we make a better estimate for every number at position $i$ from knowing what percentage (approximately) that number should be making of the total? $\endgroup$
    – Herman
    Oct 14, 2010 at 15:08
  • 2
    $\begingroup$ Stirling's formula is not going to approximate the values to hundreds or thousands of digits. Do all your multiplications and divisions with logarithms. They reduce the multiplication of two 1000-digit numbers to the addition of two values around 1000. Carry this out in double precision. $\endgroup$
    – whuber
    Oct 14, 2010 at 18:43

3 Answers 3

Reset to default
8
$\begingroup$

Are you computing the factorials and then dividing? Don't do that. You can combine the estimates you get from Stirling's formula into

$${n+m \choose n} \approx \sqrt{ \frac{m+n}{2 \pi mn} } \frac{(m+n)^{m+n}}{m^m n^n}$$

and even then you can optimize, for example rewriting the second factor as

$$\left( 1 + \frac{n}{m} \right)^m \left( 1 + \frac{m}{n} \right)^n$$

and, depending on the relative sizes of $m$ and $n$, applying the approximation $\left( 1 + \frac{x}{n} \right)^n \approx e^x$. This will work if one of $m$ and $n$ are large compared to the other and in the intermediate case the above powers should be straightforward to compute. See also Exercises 1 and 2 at this blog post by Terence Tao on the subject.

Depending on what kind of precision you need you should consider just working with the logarithms and not with the numbers directly.

$\endgroup$
1
  • $\begingroup$ A nit-shouldn't the 2*pi be in the denominator? There are two factorials there $\endgroup$
    – Ross Millikan
    Oct 14, 2010 at 15:36
7
$\begingroup$

If you want all the numbers in one particular row, you can get each from the last with one multiply and one divide. ${n \choose m}={n \choose m-1}*(n-m+1)/m$

For individual components, you can use the fact that the distribution is approximately normal with standard deviation $\sqrt n$ and the central coefficient is about $\frac {4^n}{\sqrt n\pi}$. I'm not sure that is any faster than Qiaochu's suggestion

$\endgroup$
1
  • $\begingroup$ See my comment to @Hans Lundmark's response concerning the use of the normal distribution. $\endgroup$
    – whuber
    Oct 14, 2010 at 18:59
-1
$\begingroup$

The entries in the $n$th row of Pascal's triangle (for large $n$) follow a Gaussian curve quite closely, as a consequence of the central limit theorem. See the Wikipedia article about the binomial distribution.

$\endgroup$
2
  • 4
    $\begingroup$ This is true in a narrow sense but it doesn't apply to the question. The cumulative sums of the binomial coefficients (suitably normalized) follow the cdf of a Gaussian. On a relative basis, estimates of the binomial coefficients obtained from the Gaussian are pretty good between n/2 - 2*Sqrt(n) and n/2 + 2*Sqrt(n) but become horrible outside that range, where the Gaussian grossly overestimates the binomial coefficients. The error actually gets worse as n gets large. $\endgroup$
    – whuber
    Oct 14, 2010 at 18:57
  • $\begingroup$ @whuber: I stand corrected. Thank you! $\endgroup$
    – Hans Lundmark
    Oct 15, 2010 at 6:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .