# Calculating $\sum_{j=0}^{j_{\rm max}}\prod_{m=1}^k x_{i,j,m}$ for large lists

I am struggling with the calculation of:

$\forall i\,,\sum_{j=0}^{j_{\rm max}}\prod_{m=1}^k x_{i,j,m}\,, \forall k\ge 1$

where $i\in(1,i_{\rm max})$, $i_{\rm max}$ can be up to $1000$ but usually around $3$, $k\in(1,k_{\rm max})$, $k_{\rm max}\sim 10^5$ and $j_{\rm max}\sim 20-100$. The result should have dimensions $\{i_{\rm max},k_{\rm max}\}$.

I tried two approaches but neither of which works for the dimensions mentioned above:

1. Memory very intensive:

x = RandomReal[{-2.0*10^6, 2.0*10^6}, {2, 16, 1000}]; x2 = Map[Table[#[[1 ;; i]], {i, 1, Length@#}] &, x, {2}]; // AbsoluteTiming x4 = Apply[Times, x2, {3}]; // AbsoluteTiming ByteCount@x4

2. CPU intensive (also it has an annoying feature that it produces a differently shaped list {1000,2,16})

x = RandomReal[{-2.0*10^6, 2.0*10^6}, {2, 16, 1000}]; x3 = Apply[Times, Map[Function[y, Take[y, #]], x, {2}], {2}] & /@Range[Dimensions[x][[3]]]; // AbsoluteTiming ByteCount@x3

They both work as long as the dimensions are as shown. But I ultimately need this for much bigger lists, the max size of the list can be up to {1000,20,100000} and though it is very unlikely that I will end up with such a huge list, list of the dimensions {3,20,100000} are common.

Neither of the methods mentioned above are capable of doing the product itself for the sizes mentioned so I have not yet got to the summing part along the second index.

## Update

I found FoldList: specifically (not doing the sum yet): Map[Rest[FoldList[Times, 1, #]] &, x, {2}] and it has some extraordinary results. With:

x = RandomReal[{-2.0*10^6, 2.0*10^6}, {10, 20, 100000}];
ByteCount@x


I get

x8 = Map[Rest[FoldList[Times, 1, #]] &, x, {2}]; // AbsoluteTiming
{12.4321, Null}


Can I still do it faster?

You may use ParallelMap and FoldList.

ParallelMap[

The inner ParallelMap calcuates the products of the sublist in parallel. The outer ParallelMap then calculates the sums in parallel.
Comparison using RepeatedTiming
• I am having strange results with ParallelMap: Map[FoldList[Times, #] &, x, {2}]; // AbsoluteTiming gives {2.59738, Null} while ParallelMap[FoldList[Times, #] &, x, {2}]; // AbsoluteTiming results in {73.3312, Null}. I am on linux. Can you see the same behaviour? – leosenko Mar 11 '17 at 19:26
• @leosenko Yes. I get that as well. You should report to WRI. However, when compared to the CPU intensive method in your post the ParallelMap above wins. It is odd that the two statements in your comment don't reflect that. – Edmund Mar 11 '17 at 19:45