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

Question

我试图在 O(N) 中计算它而不会溢出(使用 C++)

为了澄清，n、r 是预先给出的，我正在尝试为 (n,r) 的一个实例找到答案> 在 O(N)

中配对

这是我的试用版:

1. 使用O(N)计算ans = n!/(r!(n-r)!2^n)
2. 令c = ans，用O(N)修改c:c/= (n-p); c*=(p+1) 对于 p = r-1 到 0。为每一步添加c到ans

基本上我使用 O(N) 首先计算最后一项，然后使用类似滑动窗口的东西找到倒数第二项，然后是下一项……直到第一项。在过程中总结。

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

另一个大问题是我面临一个两难选择:对于大的 n，我无法单独计算 2^(-n) 或 nCr >，否则会下溢/上溢。这就是为什么我尝试计算 2^(-n) * The last term in the summation 和hope for 效果会相互抵消，这样我就不会下溢/在整个过程中溢出。有什么方法可以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

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

计算log(1/2**n)。

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