3

我想计算

S = n + m - \sum_{k=1}^{n} k^{k-1} \binom{n}{k} \frac{(nk)^{n+mk}}{n^{n +m-1}}

对于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
4

2 回答 2

4

似乎问题出在 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. 好像你会得到一个浮动，否则可能会搞砸。

于 2013-04-16T19:07:27.967 回答
2

scipy.misc.comb在这种情况下返回ndarray一个浮点数。其余的计算都是用整数完成的（最终在 Python < 3 中是长整数）。当将浮点数乘以 int 时，Python 尝试将其转换为浮点数，但 99**199 ~ 1e397 不适合 Python 浮点数（64 位），因此会引发错误。

一个解决方案是exact=True作为参数传递给comb. 顺便说一句，您可以删除[and ]inside sum：这避免了内部列表的创建，因此它应该更快，内存效率更高（类似于rangeand之间的区别xrange）。而且，如果您碰巧将浮点数相加（此处不需要），那么使用math.fsum(accurate floating point sum of values) 比使用sum.

于 2013-04-16T19:30:07.300 回答