如何在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)