prefix/recurse.c

   1 /*
   2  * Recursive parallel prefix with auxiliary array y
   3  */
   4 #include "recurse.h"
   5
   6 void algorithm (numtype x[], unsigned long n, unsigned int ops[]) {
   7         unsigned int i;
   8         numtype y[n/2];
   9         if (n == 1) {
  10                 return;
  11         }
  12
  13         for (i=0; i < (n/2); i++) {
  14                 y[i] = x[2*i] + x[2*i+1];
  15         }
  16
  17         algorithm(y, n/2, ops);
  18
  19         x[1] = y[0];
  20         for (i = 1; i < (n/2); i++){
  21                 x[2*i] = y[i-1] + x[2*i];
  22                 x[2*i+1] = y[i];
  23         }
  24         if ((n%2)==1) {
  25                 x[n-1] = y[n/2-1] + x[n-1];
  26         }
  27 }