# 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?

• Total[Times @@@ Tuples[lst, {size}]]? Aug 10, 2017 at 9:37

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:= sumprobAtCubed[lst__, size_] := Total[Times @@@ Tuples[lst, {size}]]

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

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

Out= {0.743279, 77114156402999}

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

Out= {4.352, 77114156402999}

In:= xxx

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

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

Out= {0.618, 77114156402999}

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

Out= {4.3, 77114156402999}

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

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

Out= {12.4336, 77114156402999}


(V.11.1 Mac OS)

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

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

Out= {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, 2017 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. Aug 10, 2017 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) Aug 11, 2017 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. Aug 11, 2017 at 16:38