如果要对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，可以方便地进行DCT处理
2. 用表达式pow（A + A * cos（Pi * n / N），O / 2初始化它
3. 应用前向DCT-I
4. 从缓冲区中读取系数-第一个数字是中心峰，其中heads = tails，随后的项对应于距中心连续的对称对

准确性

在累积的浮点舍入误差抢走系数的准确整数值之前，O的上限是有限制的，但是我想这个数字会很高。双精度浮点可以完全准确地表示53位整数，而我将忽略pow（）使用中的舍入损失，因为生成的表达式将在FP寄存器中发生，使我们额外获得了11个尾数位吸收Intel平台上的舍入误差。因此，假设我们使用通过FFT实现的1024点DCT-I，这意味着在转换过程中由于舍入误差而损失了10位的精度，并且损失不了太多，给我们留下了约43位的清晰表示。我不知道二项式展开的阶数会生成该大小的系数，但我敢说它足以满足您的需求。

不对称扩张

如果要对a和b的不相等系数进行不对称展开，则需要使用双面（复杂）DFT和复杂pow（）函数。生成表达式A * A * e ^（-Pi * i * n /
N）+ A * B + B * B * e ^（+ Pi * i * n /
N）[使用复杂的pow（）函数引发并将其扩展为展开顺序的一半）并进行DFT。同样，缓冲区中的内容是偏移量为零的中心点（但如果A和B非常不同，则不是最大值），然后是分布的上半部分。缓冲区的上半部分将包含分布的下半部分，对应于负的heads-
minus-tails值。

请注意，源数据是Hermitian对称的（输入缓冲区的后半部分是第一个的复共轭），因此此算法不是最佳算法，可以使用所需大小一半的复数到复数FFT来执行。效率。

不用说，与上面对称分布的纯实际算法相比，所有复杂的幂运算都会消耗更多的CPU时间并损害准确性。