1
$\begingroup$

The following web page: "http://introcs.cs.princeton.edu/java/78crypto/" (at Exercise 28) effectively says that:

"Pascal's triangle. One way to compute the $n$-th row of Pascal's triangle (for $n > 2$) is to compute $(2n + 1)^{n+1}$ and take its binary representation k bits at a time."

I am trying to find an efficient way of computing the binomial $n\choose{k}$ (the $n$-th row of the Pascal triangle and its $k$-th row) without having to compute the full expansion of $(2^n+1)^{n+1}$. We are assuming that $n$ is large.

One approach would be to find a way to compute the $m$-th bit of $(2^k+1)^{k+1}$ without actually having to compute the value of $(2^k+1)^{k+1}$. A Bailey-Borwein-Plouffe formula for instance...

Another approach that I considered is to use the result here: Is there a closed form expansion for $(2^k + 1)^{k+1}$?

We would then need to convert:

$ \sum_{i\in\mathcal{I} \atop j=1,...,n} c_j 2^{i},\ \ \ c_j \in \mathbb{N} $

to the canonical base-2 representation:

$ \sum_{i=1}^n b_i 2^i, \ \ \ b_i \in \{0,1\} $

For example, if we had $1+2^5+3*2^7+2^{11}+2^{12}$, we would need a method to convert it efficiently to $\sum_{i=1}^n b_i 2^i$... without having to sum all indices $i=1,...,n$ since $n$ is large.

$\endgroup$
  • $\begingroup$ Are you really just asking for "an efficient way of computing the binomial [coefficient] $n \choose k$? The usual thing to do is to use the formula $\dfrac{n!}{k!\cdot(n-k)!}$, or to use recursion: ${n \choose k}={n-1 \choose k}+{n-1 \choose k-1}$ when $0<k<n$, ${n \choose k}=1$ when $k=0$ or $k=n$, and ${n \choose k}=0$ otherwise (with memoization of intermediate values). Is that not efficient enough? (Also, you have some typos in your quotation.) $\endgroup$ – Steve Kass May 27 '14 at 0:57
  • $\begingroup$ For the $n$-th row, we would have an $O(n)$ algorithm... But since we are assuming very large values of $n$... $O(n)$ would not be efficient enough... I evaluated a method based on matrix exponentials where the best I could do is to reduce the problem to multiplying two vectors of size $n$... with the multiply-accumulate functionalities of some CPUs or DSPs, this is still a helper... this is based on the scaling and squaring method. But we then have to store the vectors... so there is a space trade-off that wasn't good enough for my purpose... $\endgroup$ – user13675 May 27 '14 at 1:14
  • $\begingroup$ Ok, see what you find searching for “efficient computation of binomial coefficient” google.com/… . For example, a bit down the results page is a paper claiming a fast way to get the result modulo a power of 2: hal.archives-ouvertes.fr/docs/00/90/41/77/PDF/… . One or more of the results might help you, depending on what you need. Is $k$ small relative to $n$, for example? Or is an answer mod something enough? Or is an approximation ok? $\endgroup$ – Steve Kass May 27 '14 at 1:24
  • $\begingroup$ Thanks for the refs... I was looking for an exact solution... and to be honest, I am even looking for a log-log space solution since in the end, I'll be doing $\log {n\choose k}$... but I am starting with just how to find the digits of $(2^n+1)^{n+1}$ without computing to full exponentiation... $\endgroup$ – user13675 May 27 '14 at 1:39

Your Answer

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

Browse other questions tagged or ask your own question.