## Closed form expression for this for loop?

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

### Closed form expression for this for loop?

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.
http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.
Sagekilla

Posts: 385
Joined: Fri Aug 21, 2009 1:02 am UTC
Location: Long Island, NY

### Re: Closed form expression for this for loop?

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;`
Last edited by Xeio on Wed Dec 28, 2011 10:28 am UTC, edited 2 times in total.

Xeio
Friends, Faidites, Countrymen

Posts: 4638
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\

### Re: Closed form expression for this for loop?

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
http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.
Sagekilla

Posts: 385
Joined: Fri Aug 21, 2009 1:02 am UTC
Location: Long Island, NY

### Re: Closed form expression for this for loop?

- 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.
mfb

Posts: 824
Joined: Thu Jan 08, 2009 7:48 pm UTC

### Re: Closed form expression for this for loop?

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.
http://en.wikipedia.org/wiki/DSV_Alvin#Sinking wrote:Researchers found a cheese sandwich which exhibited no visible signs of decomposition, and was in fact eaten.
Sagekilla

Posts: 385
Joined: Fri Aug 21, 2009 1:02 am UTC
Location: Long Island, NY

### Re: Closed form expression for this for loop?

Code: Select all
`//////////////////////////////// step 7  removing the bug from P//////////////////////int k=0;              // counter of add by pint j=(i+1) % p;   // modular value of iint 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.
tempest69

Posts: 10
Joined: Mon Oct 18, 2010 5:10 pm UTC

### Re: Closed form expression for this for loop?

tempest69 wrote: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.
roband wrote:Mav is a cow.

UniJam 2012: Inter-university Games Jam hosted by Nottingham Trent University DevSoc.
nlug: Nottingham Linux User Group
DevSoc: The Nottingham Trent University Software Development Society

The Black Hand

Posts: 1030
Joined: Tue Feb 12, 2008 11:40 am UTC
Location: Somewhere only we know

### Re: Closed form expression for this for loop?

Sagekilla wrote: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`
Goplat

Posts: 490
Joined: Sun Mar 04, 2007 11:41 pm UTC

### Re: Closed form expression for this for loop?

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?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Yakk
Poster with most posts but no title.

Posts: 10211
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Closed form expression for this for loop?

Goplat wrote:
Sagekilla wrote: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.
Hawknc wrote:Gotta love our political choices here - you can pick the unionised socially conservative party, or the free-market even more socially conservative party. Oh who to vote for…I don't know, I think I'll just flip a coin and hope it explodes and kills me.

Website

Toeofdoom
The (Male) Skeleton Guitarist

Posts: 3444
Joined: Wed Jan 10, 2007 10:06 am UTC
Location: Melbourne, Australia

### Re: Closed form expression for this for loop?

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.

Xeio
Friends, Faidites, Countrymen

Posts: 4638
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\

### Re: Closed form expression for this for loop?

tempest69 wrote: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
tempest69

Posts: 10
Joined: Mon Oct 18, 2010 5:10 pm UTC

### Re: Closed form expression for this for loop?

[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.
gribgrub

Posts: 3
Joined: Sun Dec 13, 2009 10:34 pm UTC