本文介绍如何在不依赖任何外部模块的前提下，高效、稳定地计算大规模参数（如 n=10000, m=5000）下的二项分布概率，通过乘法递推公式避免阶乘溢出与栈溢出问题。
本文介绍如何在不依赖任何外部模块的前提下，高效、稳定地计算大规模参数（如 n=10000, m=5000）下的二项分布概率，通过乘法递推公式避免阶乘溢出与栈溢出问题。
传统实现常直接调用阶乘函数（如 n! / (m! (n−m)!)），但该方式存在三大缺陷：
- 整数爆炸：10000! 是约 35660 位的超大整数，虽 Python 支持任意精度整数，但后续除法转为浮点时会因精度丢失或 OverflowError 失败；
- 栈溢出：递归阶乘（即使带 memoization）在 n=100000 时触发深度递归，超出默认递归限制；
- 性能低下：重复计算大量中间阶乘，时间复杂度达 O(n)，空间开销高。
✅ 正确解法是采用二项系数的乘法递推公式（Multiplicative Formula）：
$$ \binom{n}{m} = \prod_{i=1}^{\min(m,\,n-m)} \frac{n - i + 1}{i} $$
该公式优势显著：
- 全程整数运算：利用 // 整除确保每一步结果仍为整数，避免浮点误差累积；
- 最小化迭代次数：仅循环 min(m, n−m) 次（例如 binomial(10000, 5000) 只需 5000 次迭代）；
- 零内存缓存依赖：无需 memo 字典或递归调用，彻底规避栈溢出；
- 数值稳定：分子分母同步约简，有效抑制中间值增长。
以下是完整、健壮的实现：
立即学习“Python免费学习笔记（深入）”；
def binomial_coefficient(n, m):
"""计算组合数 C(n, m)，支持大整数，无模块依赖"""
if m < 0 or m > n:
return 0 # 统一返回 0 表示未定义（比字符串更利于数值计算）
if m == 0 or m == n:
return 1
# 利用对称性 C(n,m) == C(n, n-m)，取较小者减少循环次数
m = min(m, n - m)
result = 1
for i in range(1, m + 1):
result = result * (n - i + 1) // i # 关键：先乘后整除，保持整数性
return result
def binomial_pmf(n, m, p=0.5):
"""计算二项分布概率质量函数 P(X = m) = C(n,m) * p^m * (1-p)^(n-m)"""
if n < 0 or m < 0 or m > n:
return 0.0
# 对于公平硬币（p = 1/2），可简化为 C(n,m) / 2^n
coeff = binomial_coefficient(n, m)
# 使用 pow(2, n) 避免 2**n 在极大 n 下生成超长整数（但 Python 中仍安全）
# 更稳妥做法：直接用 float 除法（coeff 自动转为 float）
return coeff / (1 << n) # 等价于 coeff / (2**n)，位运算略快且语义清晰
# 示例验证
print(binomial_pmf(10_000, 5_000)) # 输出: 0.007978646139382154
print(binomial_pmf(100_000, 50_000)) # 可稳定运行（约数百毫秒）⚠️ 注意事项：
- 不要使用 `(1/2)n计算分母**：该表达式生成极小浮点数（如n=10000时约为1e-3010），导致下溢（underflow）为0.0，最终结果为inf或nan；应始终用1 / (2**n)或1 / (1
- // 运算符不可替换为 /：/ 返回浮点数，会引入舍入误差并破坏整数累积；// 在整数间运算时等价于数学整除，且 Python 保证 a // b * b == a 当 b 整除 a（此处恒成立）。
- 若需扩展至非公平硬币（p ≠ 0.5），建议改用对数域计算（如 log(C(n,m)) + m*log(p) + (n−m)*log(1−p)），但本题明确禁止导入模块（无法用 math.log），故推荐场景限定为 p = 0.5。
总结：面对大数二项概率计算，核心在于避开显式阶乘，转向递推组合数 + 精确整数运算。该方法兼具正确性、效率与鲁棒性，是纯 Python 环境下的最优实践。
