Closed form expression for this for loop?

[Sagekilla]

I'm reading some code and there's this one loop that's really bothering me.

Code: Select all

for (int t = 0; t < n; t++)
    i += 1 + ((i + 1) % p == 0) ? p : 0;


Where i, p, n are already provided. I feel like there should be a simpler way of writing this expression.

Well that, and this is actually taking up a significant amount of CPU time because it's being called inside
of an inner loop as the increment operation. That is, there's something like:

Code: Select all

for (int i = 0; i < end; i = DoComplicatedThing(i, p, n))
{
    // ...
}


It's not cheap to say the least. It's taking up 20% of the CPU time.

[Xeio]

Well, you can at least cut out the modulo operator during each iteration I think.

If you think about the (i+1)%p operation, this will not be influenced by adding p to i, as you will still get the same modulo result. So I think if you store the mod as a result at the beginning of the loop, you should just be able to assume it always increases by one per iteration.

Code: Select all

int mod = i % p;
for (int t = 0; t < n; t++){
    mod++;   
    if(mod == p){
        i += p;
        mod = 0;
    }
    i++;
}

You should definitely test it to make sure it puts out the same values, but I think it will work, unless I added an off by one issue for the mod calculations.

Edit: Assuming that works, you could probably turn it into a loopless version, which I was toying with, but I'm not sure there's any real benefit unless n is generally large or something.
Edit2: Fixed issue with loopless version.

Spoiler:

This might also work as a loopless version, but it's less likely to work than the first one, because there's more chance I introduced an error unrolling it. Also it's got more mult/mod operations so might be slower for small n.

Code: Select all

if(p > 1){
    i += p * (n / p);
    if(i % p == 0) i += p;
}
else{
    i += p * n;
}
i += n;


[Sagekilla]

Getting rid of the loop would be completely ideal.
Like I said before, this one, loop is eating up 20% of the cpu.

This happens to be for a lock free parallel version of an algorithm.
the majority of cpu tint is supposed to be in the actual inner loop calculation,
not the part that gets to the next value of i. But this is being a pain by eating up such a significant amount of time

Practically speaking n is like 8 (where n is the number of threads), but its running in the inner loop of two nested loops where m (5000+) iterations are done on each level.

So yeah, it kind of is a pain

[mfb]

- Determine the number m of cases where p has to be added, calculate i+=n+m*p
As only i+=1 modifies (i+1)%p, the p is added every p steps. So m is [n/p] or [n/p]+1, depending on the initial i.

Something like that:

Code: Select all

if (n%p >= (i+1)%p)
  m=[n/p];
else
  m=[n/p]+1;
i+=n+m*p;

Should be right up to mistakes of +-1, which you can check yourself.

[Sagekilla]

Agh. Both of your solutions come so close. Either one would actually be much faster than the loop.

I'll try your idea mfb. It makes sense to me now that I think about it. I just need to figure out the choice of m to use.

[tempest69]

Code: Select all

///////////////////////
///////// step 7  removing the bug from P
//////////////////////
int k=0;              // counter of add by p
int j=(i+1) % p;   // modular value of i
int t=0;              // moved for the while loop.
    if (0==j)  {k++;   i++;       j=0;} 
While (t < n){ 
    if (j==p)  {
          k++;
          i+=j+1;
          j=0;
          if ((n-t)>p){j=p; t+=p;continue;}  // skip a bunch of steps, make sure that both the [i]p-1[/i] and [i]>[/i] is the right choice.
          else{ i+=n-t; t=n;continue;}             //This is the end of the loop
     }else {
        i+=p-j;
        t+=p-j;
        [b]if (t>n){i-=n-t;break;}[/b]
        j=p;
        continue;
     }
}
i+=k*p;  // all of the add p parts.
///


ok there was a 3 page process of getting here.. but I hit save draft and got a login screen (I bloody hate a save draft button that can blank your work)

anyway there are probably some flaws in this one.
This should be fast, but is way less elegant than earlier (unseen) steps.

[RoadieRich]

ok there was a 3 page process of getting here.. but I hit save draft and got a login screen (I bloody hate a save draft button that can blank your work)

Off topic, but you should try Lazarus, an addon designed to prevent just that.

[Goplat]

I'm reading some code and there's this one loop that's really bothering me.

Code: Select all

for (int t = 0; t < n; t++)
    i += 1 + ((i + 1) % p == 0) ? p : 0;


I think that right parenthesis is misplaced - using gcc 4.1.2 at least, + has higher precedence than ?: so the loop statement is just equivalent to "i += p".

The number of times the 1+p increment is used rather than the 1 increment is (i % p + n) / p, so the code can be simplified to:

Code: Select all

i += n + (i % p + n) / p * p


[Yakk]

This happens to be for a lock free parallel version of an algorithm.

Wait, are these variables visible, read and written to, from more than one thread at once?

[Toeofdoom]

I'm reading some code and there's this one loop that's really bothering me.

Code: Select all

for (int t = 0; t < n; t++)
    i += 1 + ((i + 1) % p == 0) ? p : 0;


I think that right parenthesis is misplaced - using gcc 4.1.2 at least, + has higher precedence than ?: so the loop statement is just equivalent to "i += p".

This confused me too, but I came to the same conclusion. I haven't tested the code in anything but it definitely seems like that's exactly what it would do. But unless someone is intentionally obfuscating and slowing down code, that seems like a mistake.

[Xeio]

I guess I'm spoiled in C# where an integer value isn't valid as the left hand value of a ternary operator so I would have gotten a compiler error if I tried to pull up visual studio.

[tempest69]

ok there was a 3 page process of getting here.. but I hit save draft and got a login screen (I bloody hate a save draft button that can blank your work)

Off topic, but you should try Lazarus, an addon designed to prevent just that.

Thanks, I'm going to give it a try

[gribgrub]

[quote="Sagekilla"]I'm reading some code and there's this one loop that's really bothering me.

Code: Select all

for (int t = 0; t < n; t++)
    i += 1 + ((i + 1) % p == 0) ? p : 0;


Where i, p, n are already provided. I feel like there should be a simpler way of writing this expression.

If i = 0, then the loop will return p*(n+1)*n/2.