如何在python中计算昂贵的高精度和？

Question

我的问题很简单。我想计算一下下面的总和。

from __future__ import division
from scipy.misc import comb
import math

for n in xrange(2,1000,10):
    m = 2.2*n/math.log(n)
    print sum(sum(comb(n,a) * comb(n-a,b) * (comb(a+b,a)*2**(-a-b))**m
                    for b in xrange(n+1))
               for a in xrange(1,n+1))

但是，python提供了RuntimeWarning: overflow encountered in multiply和nan作为输出，而且速度也非常慢。

有什么聪明的办法吗？

Answer 1

你之所以得到NaNs，是因为你最终评估的数字如下

comb(600 + 600, 600) == 3.96509646226102e+359

它太大，不适合于浮点数：

>>> numpy.finfo(float).max
1.7976931348623157e+308

取对数以避免：

from __future__ import division, absolute_import, print_function
from scipy.special import betaln
from scipy.misc import logsumexp
import numpy as np


def binomln(n, k):
    # Assumes binom(n, k) >= 0
    return -betaln(1 + n - k, 1 + k) - np.log(n + 1)


for n in range(2, 1000, 10):
    m = 2.2*n/np.log(n)

    a = np.arange(1, n + 1)[np.newaxis,:]
    b = np.arange(n + 1)[:,np.newaxis]

    v = (binomln(n, a) 
         + binomln(n - a, b) 
         + m*binomln(a + b, a) 
         - m*(a+b) * np.log(2))

    term = np.exp(logsumexp(v))
    print(term)

Answer 2

使用追忆模式。在此之后，重新定义梳子：

@memoized
def newcomb(a, b):
    return comb(a, b)

并将对comb的所有调用替换为newcomb。另外，为了略有改进，去掉括号。如果列出了明确的列表，就会浪费时间来构建它们。如果您删除它们，您将有效地使用生成器表达式。

更新

这不会解决nan问题，但确实会使它变得更快。

对于那些不认为这更快的人来说，你是在申请回忆录装饰师吗？在我的机器上，最初的功能需要29.7秒才能达到200，但回忆录版本只需要3.8秒。

回忆录所做的只是将您对comb的所有调用存储在一个查找表中。因此，如果在以后的迭代中使用与过去相同的参数调用comb，那么它不会重新计算它--它只是在查找表中查找它。