Как вычислить сумму с большими промежуточными значениями

Я хотел бы вычислить

$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

2 Solutions collect form web for “Как вычислить сумму с большими промежуточными значениями”

Похоже, проблема заключается в определении comb scipy. Когда я поставляю домашнюю версию, она отлично работает:

 import math def choose(n,k): return math.factorial(n) / (math.factorial(k)*math.factorial(nk)) 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 секунды):

В качестве альтернативы написанию собственного comb попробуйте передать True для необязательного exact аргумента для comb . Похоже, вы снова получите поплавок, что может испортить ситуацию.

scipy.misc.comb возвращает ndarray одного числа с плавающей запятой в этом случае. Остальные вычисления выполняются с целыми числами (в конечном итоге длинными целыми числами в Python <3). При умножении числа с плавающей запятой на int Python пытается преобразовать его в float, но 99 ** 199 ~ 1e397 не вписывается в поплавок Python (64 бит), поэтому он вызывает ошибку.

Решение состоит в том, чтобы передать exact=True в качестве аргумента для comb . Кстати, вы можете удалить [ и ] внутри sum : это позволяет избежать создания внутреннего списка, поэтому он должен быть быстрее и эффективнее с точки зрения памяти (это похоже на разницу между range и xrange ). И если вам когда-либо приходится складывать числа с плавающей запятой (здесь не нужны), гораздо лучше использовать math.fsum (точную сумму с плавающей запятой), чем sum .