最快产生二项式系数的方法 [英] Fastest way to generate binomial coefficients

问题描述

我需要计算组合了许多。

I need to calculate combinations for a number.

什么是计算NCP最快的方法，其中n >> P？

What is the fastest way to calculate nCp where n>>p?

我需要一个快速的方式来产生二项式系数为多项式方程，我需要得到所有条款的系数，并将其存储在数组中。

I need a fast way to generate binomial coefficients for an polynomial equation and I need to get the coefficient of all the terms and store it in an array.

（A + B）^ N = A ^ N + NC1一个^（N-1）* B + NC2一个^（N-2）* ............   + NC（N-1）* B ^（N-1）+ B ^ N

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

什么是计算NCP ??最有效的方式。

What is the most efficient way to calculate nCp ??

推荐答案

如果你想完全展开对n的值很大，FFT卷积可能是最快的方式。在平等的系数二项式扩展（如一系列公平的掷硬币）和偶数阶（投掷的如数字），你可以这样利用对称的情况：

If you want complete expansions for large values of n, FFT convolution might be the fastest way. In the case of a binomial expansion with equal coefficients (e.g. a series of fair coin tosses) and an even order (e.g. number of tosses) you can exploit symmetries thus:

理论

再present两个抛硬币的结果（例如一半的头和尾巴的总数之间的差额）与前pression A + A * COS（PI * N / N）。 N是你的缓冲区的样本数 - 即使阶为O的二项展开将有O + 1的系数，并要求N> = O / 2 + 1样品的缓冲 - n是要生成的采样数，A是比例因子通常是2（用于产生二项式系数）或0.5（用于产生二项式概率分布），该

Represent the results of two coin tosses (e.g. half the difference between the total number of heads and tails) with the expression A + A*cos(Pi*n/N). N is the number of samples in your buffer - a binomial expansion of even order O will have O+1 coefficients and require a buffer of N >= O/2 + 1 samples - n is the sample number being generated, and A is a scale factor that will usually be either 2 (for generating binomial coefficients) or 0.5 (for generating a binomial probability distribution).

注意，在频率，该前pression酷似这两个硬币二项分布掷 - 有三个对称尖峰对应于号码（磁头尾巴）/ 2的位置。由于造型独立事件的整体概率分布需要卷积它们的分布，我们要卷积我们的前pression在频域，也就是相当于乘法在时域

Notice that, in frequency, this expression resembles the binomial distribution of those two coin tosses - there are three symmetrical spikes at positions corresponding to the number (heads-tails)/2. Since modelling the overall probability distribution of independent events requires convolving their distributions, we want to convolve our expression in the frequency domain, which is equivalent to multiplication in the time domain.

在换言之，通过提高我们的余弦前pression为两个抛结果到电源（例如，以模拟500掷，它提升到250的功率，因为​​它已经重新presents一对） ，我们可以安排二项分布为出现在频域中的大的多。由于这是所有真正的，甚至，我们可以替代DCT-I的DFT，以提高工作效率。

In other words, by raising our cosine expression for the result of two tosses to a power (e.g. to simulate 500 tosses, raise it to the power of 250 since it already represents a pair), we can arrange for the binomial distribution for a large number to appear in the frequency domain. Since this is all real and even, we can substitute the DCT-I for the DFT to improve efficiency.

算法

1. 决定的缓冲器大小，N，即至少为O / 2 + 1和可以方便DCTed
2. 与前pression POW（A + A * COS（PI * N / N），O / 2）
初始化它
3. 应用正向DCT-I
4. 宣读了缓冲系数 - 第一个数字是中央峰，其中头=尾巴，和后续条目从中心对应的对称先后对进一步

精度

有一个限制多高O会被之前积累的系数精确的整数值的浮点舍入误差抢你，但我猜的数字是pretty的新高。双precision浮点可以重新present 53位整数，完全准确，我要去忽略（）参与使用战俘的舍入损失，因为在发生前pression会发生在FP寄存器，给我们额外的11位尾数的吸收舍入误差在Intel平台上。因此，假设，就意味着失去了10位的精度在舍入误差，我们使用一个1024点DCT-I通过FFT实现的变换并没有太大的意外，留给我们〜43位的干净再presentation。我不知道是什么二项式扩张产生这种规模的系数，但我敢说这是为您的需求足够大。

There's a limit to how high O can be before accumulated floating-point rounding errors rob you of accurate integer values for the coefficients, but I'd guess the number is pretty high. Double-precision floating-point can represent 53-bit integers with complete accuracy, and I'm going to ignore the rounding loss involved in the use of pow() because the generating expression will take place in FP registers, giving us an extra 11 bits of mantissa to absorb the rounding error on Intel platforms. So assuming we use a 1024-point DCT-I implemented via the FFT, that means losing 10 bits' accuracy to rounding error during the transform and not much else, leaving us with ~43 bits of clean representation. I don't know what order of binomial expansion generates coefficients of that size, but I dare say it's big enough for your needs.

非对称扩展

如果你想在非对称扩展为A和B的不平等系数，你需要使用双面（复）DFT和复杂的POW（）函数。生成EX pression A * A * E ^（ - PI * I * N / N）+ A * B + B * B * E ^（+ PI * I * N / N）[使用复杂的POW（ ）函数将它提升到一半的扩展秩序]和DFT它的力量。你有什么在缓冲区是，再次，中心点（但如果A和B是非常不同的最大值）在偏移为零，并且它后跟分布的上半部分。缓冲器的上半部分将包含分配的下半部分中，对应于磁头的减去尾部的值是负的。

If you want the asymmetrical expansions for unequal coefficients of a and b, you'll need to use a two-sided (complex) DFT and a complex pow() function. Generate the expression A*A*e^(-Pi*i*n/N) + A*B + B*B*e^(+Pi*i*n/N) [using the complex pow() function to raise it to the power of half the expansion order] and DFT it. What you have in the buffer is, again, the central point (but not the maximum if A and B are very different) at offset zero, and it is followed by the upper half of the distribution. The upper half of the buffer will contain the lower half of the distribution, corresponding to heads-minus-tails values that are negative.

注意，源数据是厄米对称（输入缓冲器的后半部分是第一的复共轭），所以这个算法不是最佳的，并且可以使用的一半所需要的复杂的对复数FFT来执行尺寸，以获得最佳效率。

Notice that the source data is Hermitian symmetrical (the second half of the input buffer is the complex conjugate of the first), so this algorithm is not optimal and can be performed using a complex-to-complex FFT of half the required size for optimum efficiency.

不用说，所有复杂的幂将嚼更多的CPU时间和伤害精度相比，纯实算法对称分布的上方。

Needless to say, all the complex exponentiation will chew more CPU time and hurt accuracy compared to the purely real algorithm for symmetrical distributions above.

这篇关于最快产生二项式系数的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！