title: Parallel algorithm to compute Prefix Sum
body: <p>I am having a problem with implementing the algorithm for computing a prefix sum in parallel. Even though this algorithm has 3 steps, I am unable to write the code, as no pseudo-code is given.</p>
  
  <p>I went through various material on the web and also on stack overflow, but I didn't get the exact implementation of the algorithm as given on the <a href="http://en.wikipedia.org/wiki/Prefix_sum" rel="nofollow">wiki</a>. The wiki mentions the following:</p>
  
  <blockquote>
    <p>A prefix sum can be calculated in parallel by the following steps::</p>
    
    <ol>
    <li>Compute the sums of consecutive pairs of items in which the first item of the pair has an even index: z0 = x0 + x1, z1 = x2 + x3, etc.</li>
    <li>Recursively compute the prefix sum w0, w1, w2, ... of the sequence z0, z1, z2, ...</li>
    <li>Expand each term of the sequence w0, w1, w2, ... into two terms of the overall prefix sum: y0 = x0, y1 = w0, y2 = w0 + x2, y3 = w1, etc. After the first value, each successive number yi is either copied from a position half as far through the w sequence, or is the previous value added to one value in the x sequence</li>
    </ol>
  </blockquote>
  
  <p>Can someone please suggest a pseudo-code implementation for me to check and implement?</p>