如何在分子和分母都很大的情况下避免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

我最后使用了 scipy.misc.comb 这个函数，并在浮点数值达到 'Inf'（无穷大）时设置了一个上限。

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

如果你能接受一点点精度的损失，可以用对数来完全避免除法这一步。根据定义，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)) )