Closed form expression for this for loop?

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

Moderators: phlip, Prelates, Moderators General

Closed form expression for this for loop?

Postby Sagekilla » Wed Dec 28, 2011 9:30 am UTC

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?

Postby Xeio » Wed Dec 28, 2011 9:47 am UTC

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.
User avatar
Xeio
Friends, Faidites, Countrymen
 
Posts: 4784
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\

Re: Closed form expression for this for loop?

Postby Sagekilla » Wed Dec 28, 2011 10:24 am UTC

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?

Postby mfb » Wed Dec 28, 2011 2:33 pm UTC

- 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: 838
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Closed form expression for this for loop?

Postby Sagekilla » Wed Dec 28, 2011 5:39 pm UTC

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?

Postby tempest69 » Fri Jan 06, 2012 8:42 pm UTC

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.
tempest69
 
Posts: 11
Joined: Mon Oct 18, 2010 5:10 pm UTC

Re: Closed form expression for this for loop?

Postby RoadieRich » Sat Jan 07, 2012 12:03 am UTC

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
User avatar
RoadieRich
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?

Postby Goplat » Sat Jan 07, 2012 1:05 am UTC

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?

Postby Yakk » Sat Jan 07, 2012 12:24 pm UTC

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.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10428
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Closed form expression for this for loop?

Postby Toeofdoom » Sun Jan 08, 2012 5:24 am UTC

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
User avatar
Toeofdoom
The (Male) Skeleton Guitarist
 
Posts: 3446
Joined: Wed Jan 10, 2007 10:06 am UTC
Location: Melbourne, Australia

Re: Closed form expression for this for loop?

Postby Xeio » Sun Jan 08, 2012 3:35 pm UTC

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. :P
User avatar
Xeio
Friends, Faidites, Countrymen
 
Posts: 4784
Joined: Wed Jul 25, 2007 11:12 am UTC
Location: C:\Users\Xeio\

Re: Closed form expression for this for loop?

Postby tempest69 » Sun Jan 08, 2012 7:41 pm UTC

RoadieRich wrote:
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: 11
Joined: Mon Oct 18, 2010 5:10 pm UTC

Re: Closed form expression for this for loop?

Postby gribgrub » Fri Jan 27, 2012 3:22 am UTC

[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


Return to Coding

Who is online

Users browsing this forum: No registered users and 8 guests