当分子和分母都很大时，如何避免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: OverflowError: 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) )

你想要应用的替换是:

[1] a*b --> exp(log(a)+log(b))
[2] c/d --> exp(log(c)-log(d))

所以我相信你的重铸函数看起来像这样:

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函数并在float值达到'Inf'时设置一个上限