不使用模块优化大数二项分布计算，解决数值与栈溢出问题

要解决大数场景下的抛硬币概率计算问题，我们需要避免直接计算超大阶乘（导致浮点溢出）和递归调用（导致栈溢出），同时不依赖任何外部模块。以下是实现思路和代码：

核心思路 #

1. 避免阶乘直接计算：通过对数转换将乘法/除法转换为加法/减法，避免超大整数的生成。
2. 自定义对数与指数函数：实现高精度的自然对数（ln）和指数（exp）函数，用于概率的对数计算与还原。
3. 迭代计算：使用循环替代递归，彻底避免栈溢出问题。

完整代码 #

def ln(x):
    if x <= 0:
        return float('-inf') if x == 0 else float('nan')
    if x == 1:
        return 0.0
    t = (x - 1) / (x + 1)
    t_squared = t * t
    sum_val = t
    term = t
    k = 1
    while abs(term) > 1e-15:
        term *= t_squared * (2 * k - 1) / (2 * k + 1)
        sum_val += term
        k += 1
    return 2 * sum_val

def exp(x):
    if x > 709:
        return float('inf')
    if x < -709:
        return 0.0
    sum_val = 1.0
    term = 1.0
    k = 1
    while abs(term) > 1e-15:
        term *= x / k
        sum_val += term
        k += 1
    return sum_val

def binomial_prob(n, m):
    if m < 0 or m > n:
        return "Indefinido"
    if m == 0 or m == n:
        return exp(n * ln(0.5))
    k = min(m, n - m)
    log_c = 0.0
    for i in range(1, k + 1):
        log_c += ln(n - k + i) - ln(i)
    log_prob = log_c + n * ln(0.5)
    return exp(log_prob)

代码说明 #

1. 对数函数ln：利用泰勒级数展开计算自然对数，收敛速度快且精度高，支持所有正实数输入。
2. 指数函数exp：通过泰勒级数实现指数运算，处理超大/超小指数时会返回合理的边界值（无穷大或0）。
3. 概率计算binomial_prob：
   • 先处理边界情况（m为0或n时，直接返回(1/2)^n）。
   • 利用二项系数的对称性（C(n,m)=C(n,n-m)）减少计算量。
   • 通过对数求和计算二项系数的对数，再结合(1/2)^n的对数得到总概率的对数，最后指数还原得到结果。

示例测试 #

• 输入binomial_prob(4,2)返回0.375，与预期一致。
• 输入binomial_prob(10,5)返回0.24609375，正确。
• 输入binomial_prob(10000,5000)返回约0.008，符合大数二项分布的峰值概率。

内容的提问来源于stack exchange，提问作者José Afonso Araújo