Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It takes a long time to compute the summation below, and I'd like to know if there are some better ways to compute things faster. I have used $3$ ways to calculate, but they are very unsatisfactory. I have a list named cu with around $8000$ different members with all rational numbers, and I expect that Mathematica can give me a result with a reasonable time.

Clear[b, k, mu];
b[0] := 1;
b[k_] := ( b[k] = Sum[Binomial[k - 1, m - 1] cu[[m]] b[k - m], {m, 1, k}] );
AbsoluteTiming[ mu = ParallelTable[b[k], {k, 20}]; ]
(* {0.0090005, { ... } } *) 

As this recursive definition is not good in computing, I also try to use Faa di Bruno formula and Bell polynomial to calculate.

Clear[b, k, mu];
AbsoluteTiming[ mu = ParallelTable[BellY[Table[{1, cu[[n]]}, {n, k}]], {k, 20}]; ]
(* {0.0220012, { ... } } *)

0.02s are needed for only $20$ terms, then it will be too slow for all $5000$ terms. Hence I also think whether procedural programming implementation is useful.

Clear[b, k, mu];
AbsoluteTiming[ For[k = 1; mu = {}; mu[[0]] = 1, k <= 20, k++, 
mu = Append[mu, Sum[Binomial[k - 1, n - 1] cu[[n]] mu[[k - n]], {n, 1, k}]]]; ]
mu = List@Delete[mu, 0];
(* {0.0020001, ... } *)

Unfortunately, it is not good for more terms. Can anyone provide me some methods in Mathematica to calculate as quick as possible?

Thanks in advance.

share|improve this question
Are you sure whether you'll always get the right result when combining parallel-operations with memoization? – Coolwater Mar 29 '14 at 15:31
I have checked the results from all 3 ways and they are all equivalent. – Karho Mar 29 '14 at 15:58
Do you really need arbitrary precision? Just fiddling and converting to machine precision gets result ~10X faster. – ciao Mar 30 '14 at 0:47
It might help to add where this sum is from: did it come out of thin air, or is there some concrete problem you're trying to solve that might (probably) admit a smarter solution? E.g., there are some combinatorial objects floating in there, like Bell numbers (if all your entries were 1, the result for k is the kth Bell number which can be computed very quickly, a hint there may be a better way to skin this cat). – ciao Mar 30 '14 at 4:01
Clearly, I have asked about the sum is from different members, rather than the same 1 to get a Bell number. If not, I would not use BellY instead. – Karho Mar 31 '14 at 10:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.