如何在不溢出的情况下计算 O(n) 中前 k 个二项式系数的总和？

Question

我正在尝试在 O(N) 中计算这个而不溢出（使用 C++）

为了澄清，n、r 是事先给出的，我试图在 O(N)[=31 中找到 (n,r) 对的一个实例的答案=]

这是我的试用版：

使用O(N)计算ans = n!/(r!(n-r)!2^n)
让c = ans，用O(N)修改c：c /= (n-p); c*=(p+1)为p = r-1 to 0。将 c 添加到 ans 每一步

基本上我先使用 O(N) 计算最后一项，然后使用诸如滑动 window 之类的东西来查找倒数第二项，然后是下一项......直到第一项。过程中总结一下。

虽然看起来是正确的，但实际运行时间仍然比我预期的要慢。所以我想知道这个公式是否有任何特殊的已知技巧可以提高性能？如果不是，那么有什么办法可以减少常数因子吗？（基于以下片段）

另一个大问题是我面临一个困境：我不能单独计算 2^(-n) 或 nCr 来计算大 n，否则它会下溢/溢出。这就是为什么我尝试计算 2^(-n) * The last term in the summation 和希望效果会相互抵消，这样我就不会在整个过程中出现下溢/上溢。有什么方法可以100%保证不会下溢/上溢吗？

（如果可能，我想避免使用大整数库）

// c++ code snippet to demonstrate the idea 

double ans = 1;
for(int p=n; p>=1; p--){
  ans *= p;
  ans /= 2;
  if(p <= r) ans /= p;
  if(p <= n-r) ans /= p;
}
// now ans = n!/(r!(n-r)!2^n)
// use O(N) more time to find the ultimate ans: summation (n!/(r!(n-r)!2^n)) for r >= 0
double c = ans;
for(int p = r-1; p >= 0; p--){
  c /= (n-p);
  c *= (p+1);
  // Each new c is the next term:  n!/((r-1)!(n-r+1)!2^n)
  ans += c;
}

Answer 1

为什么不在第一个循环开始求和呢？如果第一个循环可以正确计算二项式系数，您可以将它们相加并计算分母。目前你只计算 ans=2^(-n)，因为其他操作相互抵消。

写出的总和是

1/2^n*(1+n+n*(n-1)/2+n*(n-1)*(n-2)/(2*3)+...)

两个二项式之间的商是

nC[k+1]/nC[k] = (n-k) / (k+1)

另请注意，根据二项式定理，具有上索引 r 和 n-r-1 的部分和的总和为 1。

Answer 2

为从 0 到 n 的每个 m 计算并存储 log(m!)。

计算对数(1/2**n)。

现在 p-th 和的项是 exp(log(n!)-log(p!)-log((n-p)!)+log(1/2**n )).将这些条款加在一起。

如何在不溢出的情况下计算 O(n) 中前 k 个二项式系数的总和？

How to compute sum of first k binomial coefficients in O(n) without overflow?

c++

algorithm

math

combinatorics