Fusing a triangle loop for parallelization, calculating sub-indices

Question

A common technique in parallelization is to fuse nested for loops like this

for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {

to

for(int x=0; x<n*n; x++) {
    int i = x/n; int j = x%n;

I'm wondering how I can do this to fuse a triangle loop like this

for(int i=0; i<n; i++) {
   for(int j=0; j<i+1; j++) {

This has n*(n+1)/2 iterations. Let's call the fused iteration x. Using the quadratic formula I have come up with this:

for(int x=0; x<(n*(n+1)/2); x++) {      
    int i  = (-1 + sqrt(1.0+8.0*x))/2;
    int j = x - i*(i+1)/2;

Unlike fusing the square loop this requires using the sqrt function and conversions from int to float and from float to int.

I'm wondering if there is a simpler or more efficient way of doing this? For example a solution which does not require the sqrt function or conversions from int to float or float to int.

Edit: I don't want a solution which depends on previous or next iterations. I only want solutions like int i = funci(x) and int j = funcj(x,i)

Here is some code showing that this works:

#include <stdio.h>
#include <math.h>
int main() {
    int n = 5;
    int cnt = 0;
    for(int i=0; i<n; i++) {
        for(int j=0; j<i+1; j++) {
            printf("%d: %d %d\n", cnt++, i,j);      
        }
    } printf("\n");

    int nmax = n*(n+1)/2;
    for(int x=0; x<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);
    }       
}

Answer 1

Considering that you're trying to fuse a triangle with the intent of parallelizing, the non-obvious solution is to choose a non-trivial mapping of x to (i,j):

j |\ i ->
  | \             ____
| |  \    =>    |\\   |
V |___\         |_\\__|

After all, you're not processing them in any special order, so the exact mapping is a don't care.

So calculate x->i,j as you'd do for a rectangle, but if i > j then { i=N-i, j = N-j } (mirror Y axis, then mirror X axis).

   ____
 |\\   |      |\           |\
 |_\\__|  ==> |_\  __  =>  | \
                  / |      |  \
                 /__|      |___\

Answer 2

The most sane form is of course the first form.

That said, the fused form is better done with conditionals:

int i = 0; int j = 0;
for(int x=0; x<(n*(n+1)/2); x++) {
  // ...
  ++j;
  if (j>i)
  {
    j = 0;
    ++i;
  }
}

Answer 3

I'm wondering if there is a simpler or more efficient way of doing this?

Yes, the code you had to begin with. Please keep the following in mind:

• There exists no case where floating point arithmetic is ever faster than plain integers.
• There does however exist plenty of cases where floating point is far slower than plain integers. FPU or no FPU.
• Float variables are generally larger than plain integers on most systems and therefore slower for that reason alone.
• The first version of the code is likely most friendly to the cache memory. As for any case of manual optimization, this depends entirely on what CPU you are using.
• Division is generally slow on most systems, no matter if done to plain integers or floats.
• Any form of complex arithmetic is going to be slower than simple counting.

So your second example is pretty much guaranteed to be far slower than the first example, for any given CPU in the world. In addition, it is also completely unreadable.