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

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！无济于事。任何帮助，将不胜感激！

最佳答案

如果您可以忍受很小的精度损失，则可以使用对数来完全避免除法步骤。根据定义，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)) )

关于python - 当分子和分母都很大时如何避免python中的溢出，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23796832/