Attempts at refactoring a simple integration method.

gistfile1.c

/*  Finished crunching numbers... .
 *
 *  Best here would require a processor array capable of performing
 *  32 operations in parallel to break even performance-wise.
 *
 *  Scalability above that floor looks fair, but the trade-off in
 *  power consumption is intense.
 *
 *  Serial processing on a single core and just waiting for a
 *  delayed result looks like a far more promising approach to this
 *  problem.
 */

/*  n -- a constant power of 2
 *  d -- an n-element array of data to be integrated
 */

// -- flat --

for (i = 1; i < n; i++)
  { d[i] += d[i-1]; }

// -- first attempt --
// variable-length iterations make this unlikely to optimize well

for (k = 1; k < n; k *= 2)
for (j = 0; j < n; j += 2 * k)
for (i = k; i < 2 * k; i++)
  { d[j+i] += d[j+k-1]; }

// -- second attempt --
// poor density... every other calculation is a no-op

for (p = 2; p <= n; p *= 2)
for (i = 0; i < n; i++) {
  int m = i % p;
  d[i] += (m >= p/2) * d[i - m + p/2 - 1];
}