python - 当分子和分母都很大时如何避免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 too large to convert to 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)) )