python - 如何计算中间值较大的总和

Question

我想计算

对于 n ≥ m，两个值都是 1000 以内的整数。最终结果是一个不比 n 大很多但中间值太大，python 无法处理。你怎么解决这个问题？

我定义函数如下。

from scipy.misc import comb
def S(n,m):
    return n+m-sum([k**(k - 1)*comb(n, k)*(n - k)**(n + m - k)/n**(n + m - 1) for k in xrange(1,n+1)])

例如，对于 n=m=100，我得到的错误是

RuntimeWarning: overflow encountered in multiply
  return n+m-sum([k**(k - 1)*comb(n, k)*(n - k)**(n + m - k)/n**(n + m - 1) for k in xrange(1,n+1)])
[...]
OverflowError: long int too large to convert to float

Answer 1

似乎问题出在 scipy 的 comb 中定义。当我提供自制版本时，它工作正常:

import math

def choose(n,k):
    return math.factorial(n) / (math.factorial(k)*math.factorial(n-k))

comb = choose

def S(n,m):
    return n+m-sum([k**(k - 1)*comb(n, k)*(n - k)**(n + m - k)/n**(n + m - 1) for k in xrange(1,n+1)])

print S(1000,1000)

结果(约 1.5 秒):

1844

作为编写自己的 comb 的替代方法，尝试将 True 作为可选的 exact 参数传递给 comb。看起来你会得到一个 float ，否则可能会把事情搞砸。