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.