title: Fusing a triangle loop for parallelization, calculating sub-indices
body: <p>A common technique in parallelization is to fuse nested for loops like this</p>
  
  <pre><code>for(int i=0; i&lt;n; i++) {
      for(int j=0; j&lt;n; j++) {
  </code></pre>
  
  <p>to </p>
  
  <pre><code>for(int x=0; x&lt;n*n; x++) {
      int i = x/n; int j = x%n;
  </code></pre>
  
  <p>I'm wondering how I can do this to fuse a triangle loop like this</p>
  
  <pre><code>for(int i=0; i&lt;n; i++) {
     for(int j=0; j&lt;i+1; j++) {
  </code></pre>
  
  <p>This has <code>n*(n+1)/2</code> iterations.  Let's call the fused iteration <code>x</code>.  Using the quadratic formula I have come up with this:</p>
  
  <pre><code>for(int x=0; x&lt;(n*(n+1)/2); x++) {      
      int i  = (-1 + sqrt(1.0+8.0*x))/2;
      int j = x - i*(i+1)/2;
  </code></pre>
  
  <p>Unlike fusing the square loop this requires using the <code>sqrt</code> function and conversions from int to float and from float to int.</p>
  
  <p><strong>I'm wondering if there is a simpler or more efficient way of doing this? For example a solution which does not require the <code>sqrt</code> function or conversions from int to float or float to int.</strong></p>
  
  <p><strong>Edit: I don't want a solution which depends on previous or next iterations.</strong>  I only want solutions like int <code>i = funci(x) and int j = funcj(x,i)</code></p>
  
  <p>Here is some code showing that this works:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;math.h&gt;
  int main() {
      int n = 5;
      int cnt = 0;
      for(int i=0; i&lt;n; i++) {
          for(int j=0; j&lt;i+1; j++) {
              printf("%d: %d %d\n", cnt++, i,j);      
          }
      } printf("\n");
  
      int nmax = n*(n+1)/2;
      for(int x=0; x&lt;nmax; x++) {     
          int i  = (-1 + sqrt(1.0+8.0*x))/2;
          int j = x - i*(i+1)/2;
          printf("%d: %d %d\n", x,i,j);
      }       
  }
  </code></pre>