当分子和分母都很大时如何避免python中的溢出

Question

from operator import mul    
from fractions import Fraction
import math

n = 5000

def nCk(n,k): 
  return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )

p = 2.884e-5
totP = 0
sgn = 1

print "n: " + str(n)
for r in range(1, n):
    numTerms = nCk(n,r) - ((2*n-3)*(r-1))
    totP += sgn * (p ** r) * numTerms
    sgn *= -1

print "total = " + str(totP)

当我开始增加n:overflowerrror:long int太大而无法转换为float时，我得到了一个溢出错误

numTerms项变得非常大，p^r项变得非常小。基本上，我有一个大分子除以一个大分母。关于如何计算这个值有什么建议吗？我考虑过用对数和斯特林近似公式计算n！无济于事。任何帮助都将不胜感激！在

Answer 1

如果您可以容忍非常轻微的精度损失，可以使用对数来完全避免除法步骤。根据定义，a/b等于exp(log(a)-log(b))。这可以在非常广泛的输入范围内工作，而不会溢出或下溢。在

要将其放在原始代码的上下文中，您需要：

return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )

要应用的替换包括：

^{pr2}$

所以我相信你的重铸功能应该是这样的：

from operator import add
from math import exp, log
...

return int( exp(reduce(add, (log(n-i)-log(i+1) for i in range(k)), 1)) )

Answer 2

要处理高精度，可以使用decimal库：

import decimal
decimal.getcontext().prec = 100 #Or whatever precision you want...
...
p = decimal.Decimal(2.884e-5)
...

虽然代码很慢，但在我的电脑上还没有停止。。。在

最后完成了，并且意识到：你打印出str(p)，而且你永远不会改变它。。。也许你是说totP？在

Answer 3

最后我用了scipy.misc.comb函数并在浮点值达到“Inf”时设置上限。在