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

Похоже, проблема заключается в определении 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 секунды):

 1844 

В качестве альтернативы написанию собственного 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 .