生成二项式系数的最快方法

Question

我需要计算一个数字的组合。

计算nCp在哪里n>>p的最快方法是什么？

我需要一种快速生成多项式方程二项式系数的方法，我需要得到所有项的系数，并将其存储在一个数组中。

(a+b)^n = a^n + nC1 a^(n-1) *b+ nC2 a^(n-2) *.+nC(n-1) a* b^(n-1) + b^n

计算nCp最有效的方法是什么?？

Answer 1

如果要对n的大值进行完全展开，FFT卷积可能是最快的方法。在系数相等的二项式展开(例如，一系列公平的硬币抛出)和偶数阶(例如掷硬币数)的情况下，你可以利用对称：

理论

用表达式A+ A*cos(Pi*n/N)表示两个硬币抛出的结果(例如，正面和尾部总数之间的差的一半)。N是缓冲区中的样本数--偶数阶O的二项式展开将具有O+1系数，需要N个>= O/2 +1样本的缓冲区-n是生成的样本数，而A是一个标度因子，通常是2(生成二项数系数)或0.5 (生成二项式概率分布)。

注意，在频率上，这个表达式类似于这两个硬币抛出的二项分布--在对应于数(正面-尾部)/2的位置上有三个对称的尖峰。由于模拟独立事件的总体概率分布需要将它们的分布进行卷积，所以我们希望在频域中将我们的表达式转换成时域中的乘法。

换句话说，通过将两次抛出的结果的余弦表达式提高到一个幂(例如模拟500次抛出，将其提高到250次，因为它已经代表一对)，我们可以安排大量的二项分布出现在频域中。由于这一切都是真实的，甚至，我们可以用DCT-I代替DFT来提高效率。

算法

1. 确定缓冲区大小N，即至少O/2 +1，并且可以方便地使用DCTed。
2. 用表达式pow(A + A*cos(Pi*n/N)，O/2)初始化它
3. 应用前向DCT-I
4. 从缓冲器中读出系数--第一个数字是heads=tails的中心峰值，随后的条目对应于距离中心更远的对称对。

精度

在累积浮点四舍五入误差之前，O的值是有限的，但我想这个数字相当高。双精度浮点可以完全精确地表示53位整数，我将忽略使用pow()所涉及的舍入损失，因为生成表达式将发生在FP寄存器中，给我们额外的11位尾数来吸收Intel平台上的舍入误差。所以假设我们使用的是1024点的DCT-我通过FFT实现了，这意味着在变换过程中由于舍入误差而失去10位的精度，而没有太多其他的，这就给我们留下了43位的清晰表示。我不知道二项式展开的顺序会产生这样大小的系数，但我敢说它足够大，可以满足你的需要。

非对称展开

如果您希望对a和b的不等系数进行非对称展开，则需要使用一个双边(复) DFT和复pow()函数。使用复pow()函数生成A*A*e^(-Pi*i*n/N) + A*B +B*e^(+Pi*i*n/N)表达式，将其提高到展开阶的一半的幂和DFT。缓冲区中的中心点(如果A和B相差很大，则不是最大值)位于偏移零点，然后是分布的上半部分。缓冲区的上半部分将包含分布的下半部分，对应于负的正负尾值。

请注意，源数据是Hermitian对称的(输入缓冲器的下半部分是第一个的复共轭)，因此该算法不是最优的，可以使用所需大小为最佳效率一半的复复FFT来执行。

不用说，与上述对称分布的纯实数算法相比，所有复杂的指数运算都会占用更多的CPU时间并损害精度。

Answer 2

您可以使用动态规划来生成二项式系数。

您可以创建一个数组，而不是使用O(N^2)循环来填充它。

C[n, k] = C[n-1, k-1] + C[n-1, k];

哪里

C[1, 1] = C[n, n] = 1

之后，在您的程序中，您可以得到C(n，k)值，只需查看在n，k索引处的2D数组。

更新是这样的

for (int k = 1; k <= K; k++) C[0][k] = 0;
for (int n = 0; n <= N; n++) C[n][0] = 1;

for (int n = 1; n <= N; n++)
   for (int k = 1; k <= K; k++)
      C[n][k] = C[n-1][k-1] + C[n-1][k];

其中，你的N，k的最大值

Answer 3

如果你需要计算所有的n，Ribtoks的答案可能是最好的。对于单个n来说，你最好这样做：

C[0] = 1
for (int k = 0; k < n; ++ k)
    C[k+1] = (C[k] * (n-k)) / (k+1)

如果在乘法后进行除法，则除法是精确的。

注意，不要满溢的Ck *(N)：使用足够大的整数。