title: Improving a binning algorithm without using arrays
body: <p>Premise: Algorithm <strong>B</strong> introduced below is the raw algorithm that stays behind a binning procedure in a Monte Carlo simulation.</p>
  
  <p>I have an algorithm <strong>A</strong> that outputs, indipendently and in an ordered sequence (i.e, not contemporary), <em>n</em> generically different values for the same single variable; this means that if not stored anywhere, a single value is swept away by the next one. These values need to be processed by an algorithm <strong>B</strong>, which works in the following way:</p>
  
  <p>1) Average over couples of contiguous values (i.e, the first with the second, the third with the fourth, and so on);<br>
  2) Determine the standard deviation of the newly obtained <em>n/2</em> values and store it away;<br>
  3) Set <em>n = n/2</em>;<br>
  4) Return to point (1) if <em>n > 1</em>.  </p>
  
  <p>I have successfully managed to implement algorithm <strong>B</strong> in c++ by storing the <em>n</em> initial values in a first array with <em>n</em> entries and the standard deviations in a second array of variable size; however, since I want <em>n</em> to be arbitrary large, it seems to me that this solution is not the best one.<br>
  Thus my question: is there any other way I can implement algorithm <strong>B</strong> without storing the <em>n</em> values in an array?</p>
  
  <hr>
  
  <p>Edit: Here follows an example of how algorithm <strong>B</strong> works with the n-size array.</p>
  
  <pre><code>int n; //Number of values.
  double * first_array = new double[n]; //Array in which every single value given by Algorithm A is stored.
  do
  {
    for (int x = 0; x &lt; n/2; x++)  //As in point (1).
       first_array[x] = (first_array[2*x] + first_array[2*x + 1])/2.0;
    ... //Here I put the values in first_array in an appropriate function to obtain the standard deviation of this single set of values and store it away as in (2).
    n = n/2; //As in point (3).
   } while (n &gt; 1); //As in point (4).
  </code></pre>