# Faster sum of products of tuples?

My function:

  sumprob[lst_,size_]:=Sum[Product[x,{x,part}],{part,Tuples[lst,{size}]}];


Example:

   sumprob[Range[1, 50, 3], 5]


13865791015625

How might I speed this up?

For optimization, worth playing around with and comparing a few different almost identical ways of doing the same thing. What seems like just syntactic sugar can sometimes cost:

In[1]:= sumprobAtCubed[lst__, size_] := Total[Times @@@ Tuples[lst, {size}]]

In[2]:= sumprobAtMap[lst__, size_] := Total[(Times @@ #) & /@ Tuples[lst, {size}]]

In[3]:= AbsoluteTiming[sumprobAtMap[xxx = RandomInteger[{1, 50}, 20], 5]]

Out[3]= {0.743279, 77114156402999}

In[4]:= AbsoluteTiming[sumprobAtCubed[xxx, 5]]

Out[4]= {4.352, 77114156402999}

In[5]:= xxx

Out[5]= {45, 48, 49, 17, 25, 8, 50, 31, 32, 27, 33, 36, 43, 16, 30, 35, 33, 29, 9, 3}

In[6]:= RepeatedTiming[sumprobAtMap[xxx, 5]]

Out[6]= {0.618, 77114156402999}

In[7]:= RepeatedTiming[sumprobAtCubed[xxx, 5]]

Out[7]= {4.3, 77114156402999}

In[8]:= sumprob[lst_, size_] := Sum[Product[x, {x, part}], {part, Tuples[lst, {size}]}];

In[9]:= AbsoluteTiming[sumprob[xxx, 5]] (* Compare with poster's orig *)

Out[9]= {12.4336, 77114156402999}


(V.11.1 Mac OS)

Edit: Thanks ciao -- solving the problem should always win ;-)

In[14]:= AbsoluteTiming[Tr[xxx]^5]

Out[14]= {0.000017, 77114156402999}

• I'd venture the version with map is getting auto-compiled. In any case, away from machines so can't test but seems like sumthing[l_,s_]:=Tr[l]^s; should do the trick quickly... – ciao Aug 10 '17 at 11:17
• @ciao I think you're right re: auto-comp. Worth including a link to this question on compilation where Leonid Shifrin's answer has a nice discussion of Map and auto-compile. – John Joseph M. Carrasco Aug 10 '17 at 11:44

Although not as fast as ciao's formula the direct computation can be done more quickly like this, assuming the input list is all positive numbers:

sumprob2[lst_, size_] := Tr @ Exp @ Total[Tuples[N @ Log @ lst, {size}], {2}];

sumprob2[Range[1, 50, 3], 5] // Round // RepeatedTiming

{0.0511, 13865791015625}


Reference:

• I like this, and nice reference. Perhaps worth warning about introduction of finite-precision arithmetic for speedup due to the N[#]&. I.e. Combined with the exp and log games, something like sumprob2[{10^4},5] will have an error of $O(10^5)$, so best with small integers etc. Still great trick, thanks for sharing! (+1) – John Joseph M. Carrasco Aug 11 '17 at 14:23
• @John Good point, I should have warned of that. Old habits from Project Euler coming through, where I would use machine precision by default and check my answer, and only if it were wrong examine round-off errors. Of course that's not a good way to proceed in general. – Mr.Wizard Aug 11 '17 at 16:38