Most Efficient Way to Calculate the Product of All Items in a List?

Say that I have a list of returns on a financial asset over time and want to know the total compounded return. To get the answer, I need to add 1 to each return and then calculate the product of all of them. So, I'm looking for a function like Total, except that it computes the product. The Product function works, but seems clumsy and slower than my alternatives (at first, I was having trouble getting Product to work, so I wrote a few of my own functions). Here are the alternatives:

listProduct[x_List] := Exp[Total[Log[x]]];
listProduct2[x_List] := Last[FoldList[Times, 1, x]];
listProduct3[x_List] := Fold[Times, 1, x];
listProduct4[x_List] := Product[x[[i]], {i, 1, Length[x]}];


Those are in the order that I thought of them. A couple of surprising things: The first seems to be the fastest by quite a lot (though none are super slow). The slowest is the last one using Product, which I thought would be highly optimized and fast.

Here are my tests:

s = RandomVariate[NormalDistribution[0.05, 0.1], 10^6];
listProduct[1 + s] - 1; // AbsoluteTiming
listProduct2[1 + s] - 1; // AbsoluteTiming
listProduct3[1 + s] - 1; // AbsoluteTiming
listProduct4[1 + s] - 1; // AbsoluteTiming


which produces these results:

{0.0312000, Null} {1.4820026, Null} {1.4040025, Null} {1.8252032, Null}


So, the question is: Is there a faster way, and am I missing some built-in function that would do this better? I won't be using lists this long, but I may be doing a lot of lists if I can get the rest of my idea implemented.

-

The function you're looking for is Times. Use it as Times@@list, or keeping in line with your functions,

listProduct[x_List] := Times @@ x

-
Excellent. I knew there must be a more elegant way to do it. I'm still new to MMA and haven't quite wrapped my head around Apply (until now), so this didn't even occur to me. This is still slower than the first method, but I like the elegance of it. Thanks! – Tim Mayes Feb 5 '12 at 7:04
@TimMayes That's correct, but if your list is a list of integers, then this will be much faster than any of your solutions (perhaps, the fastest of all). Try it with s = RandomInteger[10^3, 10^6];. Note: your solutions 2,3,4 are extremely slow with this, so I would just accept it and skip the waiting and test only with your first method and mine. – rm -rf Feb 5 '12 at 7:23
@Tim just get into the habit of thinking about Apply replacing heads. So if you have List[x1,x2,x3,...] if you replace the head List with Times you now have Times[x1,x2,x3,...] – Mike Honeychurch Feb 5 '12 at 7:26
Very interesting. It is several times faster with integers. That is more inline with what I would expect. Unfortunately, I'm not using integers, but I'll try to remember this. – Tim Mayes Feb 5 '12 at 7:33
@TimMayes by way of another example, before Total was added to Mma people used to do Plus@@{x1,x2,x3,...} which gives Plus[x1,x2,x3,...] – Mike Honeychurch Feb 5 '12 at 7:51
show 1 more comment

Apply[Times, list] is the canonical Mathematica way to represent applying an operation (such as multiplication) to the elements of a list.

Since your question asked about the most efficient way to calculate the product, I will point you to this previous question on Stack Overflow which discussed this issue at length.

The upshot is

• If the elements of the list are all machine precision integers, reals or complexes stored in a PackedArray and the result will be small enough to be representable as a machine precision number as well, then a specialized function created with Compile is going to be the fastest.

If you have a C compiler and Mathematica 8, you can also automatically compile all the way to C code as:

compiledlistproduct = Compile[{{l, _Real, 1}},
Module[{tot = 1.}, Do[tot *= x, {x, l}]; tot], CompilationTarget -> "C"]


A temporary DLL is created and linked back into Mathematica at run-time. The result will be essentially as fast as dedicated Mathematica functions like Total.

• If the result might be too large to be represented as a machine number, but you are happy with an approximate real/complex-valued result (even if the underlying objects are exact integers), then Exp[Total[Log[N[list]]]] or some variant on it (such as a custom Compiled function doing something similar) is the next thing to try.

• The Log operation keeps numbers in range of faster machine arithmetic for longer.
• The N (documentation) in N[list] turns exact integers into fast approximate machine reals (so you don't end up with relatively slow exact quantities like Log[2]).
• Otherwise go with Apply[Times, list].

See the Stack Overflow post linked above for more details, timings, and links to more related questions.

-
 Thanks for the explanation. I was baffled by why my method of using Logwould be so fast since it is using several operations. Your second point gets to that. – Tim Mayes Feb 5 '12 at 18:33 Actually Exp[Total[Log[N[list]]]] should be used (using N[list] instead of list) to turn a machine integer array (for which Log will give slower exact results like Log[2]) into a fast machine real array (like Log[2.0], which evaluates straight to a machine real). I will a correction to my answer for that. – Andrew Moylan Feb 5 '12 at 20:06 Talking about compiling, this also sounds like something that could be tackled with a CUDA routine if your need for speed is so great as to warrant the additional effort to implement this. Speculative: Maybe one could even use something like ImageMultiply or CUDAImageMultiply together with clever partitioning as a starting point? – Yves Klett Feb 6 '12 at 8:38

I asked essentially the same question on StackOverflow when I was dissatisfied with the speed of Times @@ list on a packed array. Please read the answers to that question for some really good information. Ultimately I came away with this as the fastest sign-aware list product function for Mathematica 7:

listProd = (-1)^(-1 /. Rule @@@ Tally@Sign@# /. -1 -> 0) * Exp@Total@Log@Abs@# &;


Timings:

list = RandomReal[{-1, 1}, 1*^7];

Times @@ list // Timing
listProd @ list // Timing

{0.858, -9.16325884049*10^-4340292}

{0.078, -9.1632601*10^-4340292}


As you can see a certain loss of precision occurs, but computation is more than an order of magnitude faster.

-
 I think it should be 1 /. Rule ... – rm -rf♦ Feb 5 '12 at 23:42 @R.M actually that isn't correct either (I believe). This was written assuming negative numbers in the list, and it fails in the case where there aren't any. I shall fix this later today if I have time. – Mr.Wizard♦ Feb 6 '12 at 2:09 Yeah, I wasn't entirely sure either — just noticed that it fails if there aren't any negative numbers, whereas using 1 gave the result in all my test cases. – rm -rf♦ Feb 6 '12 at 2:15 @R.M function updated; please see if it appears correct to you now. – Mr.Wizard♦ Feb 6 '12 at 2:34 Wow, this is the kind of thing that I marvel at. Beautiful, but I'll need to upgrade my MMA skills before I'd be comfortable using it even knowing that it works. – Tim Mayes Feb 6 '12 at 7:00
show 1 more comment