python之计算具有巨大中间值的总和_编程设计

我想计算

n 的值最大 1000000 尽可能准确。这是一些示例代码。

from __future__ import division 
from scipy.misc import comb 
def M(n): 
    return sum(comb(n,k,exact=True)*(1/n)*(1-k/n)**(2*n-k)*(k/n)**(k-1) for k in xrange(1,n+1)) 
for i in xrange(1,1000000,100): 
    print i,M(i)

第一个问题是当 n = 1101 时，我得到了 OverflowError: long int too large to convert to float。这是因为 comb(n,k,exact=True) 太大而无法转换为 float 。然而，最终结果始终是 0.159 左右的数字。

我在 How to compute sum with large intermediate values 问了一个相关问题然而，由于三个主要原因，这个问题有所不同。

我要计算的公式不同，这会导致不同的问题。
之前提出的使用 exact=True 的解决方案在这里没有帮助，这在我给出的示例中可以看出。编写我自己的 comb 实现也行不通，因为我仍然需要执行浮点除法。
我需要计算比以前大得多的值的答案，这会导致新问题。我怀疑如果不以某种巧妙的方式对总和进行编码，就无法完成。

不会崩溃的解决方案是使用

from fractions import Fraction 
def M2(n): 
    return sum(comb(n,k,exact=True)*Fraction(1,n)*(1-Fraction(k,n))**(2*n-k)*Fraction(k,n)**(k-1) for k in xrange(1,n+1)) 
for i in xrange(1,1000000,100): 
    print i, M2(i)*1.0

不幸的是，它现在太慢了，我无法在合理的时间内得到 n=1101 的答案。

所以第二个问题是如何让它足够快以完成大的n。

请您参考如下方法:

您可以使用对数变换计算每个被加数，该对数变换分别用加法、减法和乘法代替乘法、除法和求幂。

def summand(n,k): 
    lk=log(k) 
    ln=log(n) 
    a=(lk-ln)*(k-1) 
    b=(log(n-k)-ln)*(2*n-k) 
    c=-ln 
    d=sum(log(x) for x in xrange(n-k+1,n+1))-sum(log(x) for x in xrange(1,k+1)) 
    return exp(a+b+c+d) 
 
def M(n): 
    return sum(summand(n,k) for k in xrange(1,n))

请注意，当 k=n 时，被加数将为零，因此我不计算它，因为对数未定义。