# How does Accumulate work?

Accumulate can be used to compute the partial sums of a list.

The partial sums can also be computed using a For loop but this method should not be used according to following answer.

I have the following questions:

• Why is Accumulate much faster than using a For loop?

Please give a more elaborate answer than the fact that Mathematica is inherently a functional programming language.

• What is the exact algorithm for Accumulate?
• Can this algorithm be used in object-oriented languages (I am familiar with C++) to compute partial sums of an array faster than a for loop? If no, then why not? If yes, then how much will the performance gain (big-O notation is preferable) in C++ be compared to Mathematica?

P.S. I am not very familiar with algorithm stability so if that is a part of your answer, please provide links/details on the same.

-
Its possible that Accumulate uses memorization.For loops are somewhat inefficient in M at times.You can achieve same using FoldList which again probably uses memorization. – Rorschach Oct 6 '13 at 9:18
OOP is matter of relevance if you need entities to be represented as classes. You can use threads. First divide list as sublists and them carry out computation on each with different waiting thread. – Rorschach Oct 6 '13 at 9:43
@Blackbird , I am also using memorization, i.e., the previous partial sum is stored in a list called the partial sum list while using the For loop method. – varun Oct 6 '13 at 11:26
The algorithmic details of Accumulate is only known to us as far as the documentation goes: no one outside of WRI is able to reverse engineer it. On the other hand, built-in functions are usually faster than user-implemented ones because they are written in either low-level Mathematica or directly in C. Try compiling your code to C and see whether you get closer to Accumulate's timing. – István Zachar Oct 6 '13 at 11:28
I love knowing and trying to figure out what goes on under-the-hood, but as an intellectual property developer, I do feel an uncomfortable twinge at full-on reverse engineering. It makes me feel (just a little) like we've cheated on the love of our lives. That said, +1 for an interesting question. – Jagra Oct 6 '13 at 15:24

Using Accumulate for 20,000,000 size list. Time < 1 Hour

Your timings seem way too high. On my PC, Accumulate on an 20.000.000-element packed array takes about 50ms. A For loop (not compiled!) needs about one minute for 20 million values. My PC may be fast, but not that fast. Make sure your array contains only machine-precision reals and is packed. Otherwise, any comparison with C or C++ doesn't make much sense, because values in a C++ double* array are always machine precision and "packed".

Why is Accumulate much faster than using a For loop?

Because your For loop is written in an interpreted language, while Accumulate is (presumably) written in a low-level language; It might even use special SIMD CPU instructions that process multiple values in a single instruction. The interpreted loop on the other hand needs more than one CPU instruction just for a single addition.

What is the exact algorithm for Accumulate?

As others said in the comments, we don't know. But the obvious algorithm (take each element from the input buffer, add it to an accumulator register, store it in the output buffer) needs n read operations, n-1 add operations and n write operations. And I don't see how you could get the right result without reading each input data, writing each output value and adding n-1 values. So my guess would be that Mathematica does something like that.

Can this algorithm be used in object-oriented languages (I am familiar with C++) to compute partial sums of an array faster than a for loop?

C++ has a library function partial_sum, and (at least in my implementation) that's exactly how it's implemented.

If yes, then how much will the performance gain (big-O notation is preferable) in C++ be compared to Mathematica?

Any decent algorithm will be O(n). Probably your For loop is O(n), too.

If the question really was: Will a C++ implementation be faster, slower or just as fast as Mathematica's Accumulate, then the answer depends mostly on how smart your C++ compiler is. My guess is that any modern CPU can add numbers much faster than it can read/write them from and to main memory. So performance depends on things like whether the C++ compiler is smart enough to make the CPU prefetch values from main memory to cache before it needs them. If it is, and if Mathematica's implementation does the same, they might just be equally fast.

-
I'm sorry the time includes plotting times also. I just included the figures as a reference for comparison of order of magnitude. I'm sorry for that. I'll remove the figures from the question as they are not directly related. – varun Oct 7 '13 at 7:47

I did this experiment last year, it wasn't supposed to be very scientific:

n = 50000;
i = 1; factorial1 = 1;
Whiletime = First@Timing[While[i <= n, factorial1 *= i++]];
factorial2 = 1;
Fortime = First@ Timing[For[i = 1, i <= n, ++i, factorial2 *= i]];
factorial3 = 1;
Dotime = First@Timing[Do[factorial3 *= i, {i, 1, n}]];
Functionaltime1 =
First@Timing[factorial4 = Fold[Times, 1, Range[n]]];
Functionaltime2 = First@Timing[factorial5 = Times @@ Range[n]];
Mathematicatime = First@Timing[factorial6 = Factorial[n]];
factorial1 == factorial2 == factorial3 == factorial4 == factorial5 == factorial6


True

BarChart[{Whiletime, Fortime, Dotime,  Functionaltime1,
Functionaltime2, Mathematicatime},
ChartLabels -> {"Whiletime", "Fortime", "Dotime",
"Functionaltime1", "Functionaltime2", "Mathematicatime"},
ChartStyle -> "Pastel"]


One reason for the For and While expressions being slower is presumably that each loop is doing comparisons, assignments, testing for overflow/integer type/reassignment, and other high-level features. The Do loop has dropped the comparison, and looks to be quicker. Better performance can be achieved by using Mathematica's built-in functions wherever possible, or at least by using a more functional style.

-