optimization math computation (multiplication and summing)
- by wiso
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?
