本文介绍一种无需导入任何模块、避免阶乘溢出与递归栈溢出的优化方法，通过乘法递推公式直接计算大数二项系数，并结合幂次缩放求得精确概率值。
本文介绍一种无需导入任何模块、避免阶乘溢出与递归栈溢出的优化方法，通过乘法递推公式直接计算大数二项系数，并结合幂次缩放求得精确概率值。
在处理大规模二项分布问题（如 $ n = 10^5, m = 5\times10^4 $）时，传统基于阶乘实现（n! / (m! (n−m)!)）会迅速失效：一方面，factorial(100000) 产生远超 Python float 表示范围的整数，强制转为浮点后精度尽失；另一方面，递归记忆化阶乘仍会因深度调用（约 10⁵ 层）触发栈溢出（Windows fatal exception: stack overflow）。
根本解法在于避开显式阶乘计算，改用二项系数的乘法递推公式：
$$ \binom{n}{m} = \prod_{i=1}^{\min(m,\,n-m)} \frac{n - i + 1}{i} $$
该公式利用组合数的对称性 $\binom{n}{m} = \binom{n}{n-m}$，只迭代较小的一半项（最多 $ \lfloor n/2 \rfloor $ 次），且每一步均采用整数乘除交替，保证中间结果始终为整数、无精度损失。关键在于使用整数除法 //（因累积乘积恒被当前 i 整除），避免浮点误差。
以下是完整、健壮、零依赖的实现：
def binomial_coefficient(n, m):
"""计算 C(n, m)，使用乘法递推避免大阶乘"""
if m < 0 or m > n:
return 0 # 或 raise ValueError("Invalid parameters")
if m == 0 or m == n:
return 1
# 利用对称性减少迭代次数
m = min(m, n - m)
result = 1
for i in range(1, m + 1):
result = result * (n - i + 1) // i
return result
def binomial_pdf(n, m):
"""计算公平硬币下 P(X = m) = C(n,m) / 2^n"""
if m < 0 or m > n:
return 0.0
coeff = binomial_coefficient(n, m)
# 直接计算 2**n 可能极大，但 Python int 支持任意精度；
# 若需更高性能（如 n > 1e6），可改用对数域或近似（如Stirling），但此处不引入额外模块
denominator = 1 << n # 位运算等价于 2**n，更快更清晰
return coeff / denominator
# 示例：验证大参数可行性
print(binomial_pdf(10_000, 5_000)) # 输出: 0.007978646139382154
print(binomial_pdf(100_000, 50_000)) # 可稳定运行（耗时约数百毫秒，取决于硬件）注意事项与优化提示：
- ✅ 整数安全：循环中 result * (n - i + 1) // i 始终为整数，因二项系数本身为整数，且乘除顺序确保整除成立（数学上可证）。
- ⚠️ 性能边界：当 n 超过 $10^6$ 时，2**n 的位宽达百万比特，coeff / denominator 的浮点转换可能变慢；此时建议改用 math.log（若允许单模块）或 decimal 模块，但本方案严格满足“零模块”要求。
- ? 避免浮点中间量：切勿写成 result *= (n - i + 1) / i（引入浮点误差），必须用 // 保持整数精度。
- ? 对称优化必要：m = min(m, n - m) 将最坏迭代次数从 $O(n)$ 降至 $O(n/2)$，对 $n=10^5$ 直接减半计算量。
该方法兼具数学严谨性与工程实用性，是纯 Python 环境下处理超大二项概率问题的推荐范式。
