Suppose you want to compute the sum of the square of the differences of items:

$\sum_{i=1}^{N-1} (x_i - x_{i+1})^2$,

the simplest code (the input is std::vector<double> xs, the ouput sum2) is:

double sum2 = 0.;
double prev = xs[0];
for (vector::const_iterator i = xs.begin() + 1;
 i != xs.end(); ++i)
{
sum2 += (prev - (*i)) * (prev - (*i)); // only 1 - with compiler optimization
prev = (*i);
}

I hope that the compiler do the optimization in the comment above. If N is the length of xs you have N-1 multiplications and 2N-3 sums (sums means + or -).

Now suppose you know this variable:

sum = $x_1^2 + x_N^2 + 2 sum_{i=2}^{N-1} x_i^2$

Expanding the binomial square:

$sum_i^{N-1} (x_i-x_{i+1})^2 = sum - 2\sum_{i=1}^{N-1} x_i x_{i+1}$

so the code becomes:

double sum2 = 0.;
double prev = xs[0];
for (vector::const_iterator i = xs.begin() + 1;
 i != xs.end(); ++i)
{
sum2 += (*i) * prev;
prev = (*i);
}
sum2 = -sum2 * 2. + sum;

Here I have N multiplications and N-1 additions. In my case N is about 100.

Well, compiling with g++ -O2 I got no speed up (I try calling the inlined function 2M times), why?