Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Reversing the order of some loops.

Reply
Thread Tools

Reversing the order of some loops.

 
 
Dr. David Kirkby
Guest
Posts: n/a
 
      10-22-2003
I have a program that loops through and changes all the elements on an
array n times, so my code looks like this:

for (n=1; n < n_max; ++n)
for(i=imax; i >= 0; --i) {
for(j=0 ; j < jmax; ++j) {
/* main bulk of code goes here */
}
}

The problem is I want to reverse the order of the **two inner loops**,
so I have all 4 possible combinations of the loops incrementing and
decrement i and j. So on the first iteration of n (n=1), i and j will
both incremnt from 0 to their maximum values, but on another they will
decmement from their maximum values to 0. The second permetation would
be:

for(i=imax; i >= 0; --i) {
for(j=0 ; j < jmax; ++j) {
/* loads of code goes here */
}
}

where I have reversed the i loop, and this one where the j loop is
reversed. The other two combinations would be:

for(i=0; i< imax; ++i) {
for(j=jmax ; j >= 0; --j) {

And finally:

for(i=imax; i >= 0; --i) {
for(j=jmax ; j >= 0; --j) {

Can anyone find a ***neat*** way of doing this in a C function?


The only way I have found to do this is at the minute is rather ugly.
I have a C function (which could be main), with four #includes, and
four #defines, which includes a C source file. The exact ordering of
the loops in the included file depends on what is #defined in the main
file. In other words I have:


int main()
{
for(n=1; n < n_max; ++n) {

#define TO_BOTTOM_RIGHT
#include "update_voltage_array.c"
#undef TO_BOTTOM_RIGHT

#define TO_BOTTOM_LEFT
#include "update_voltage_array.c"
#undef TO_BOTTOM_LEFT

#define TO_TOP_RIGHT
#include "update_voltage_array.c"
#undef TO_TOP_RIGHT

#define TO_TOP_LEFT
#include "update_voltage_array.c"
#undef TO_TOP_LEFT
}


then in the file "update_voltage_array.c", I don't have a function,
but bits like this:

#ifdef TO_BOTTOM_RIGHT
for(i= 0; i <= imax; ++i){
for(j=0; j<=jmax; ++j) {
#endif

#ifdef TO_BOTTOM_LEFT
for(i= imax; i >=0 ; --i){
for(j=0; j<=jmax; ++j) {
#endif

#ifdef TO_TOP_RIGHT
for(i= 0; i <= imax; ++i){
for(j=height-1; j>=0; --j) {
#endif

#ifdef TO_TOP_LEFT
for(i= imax; i >=0; --i){
for(j=jmax; j>=0; --j) {
#endif


Can anyone think of a better way of achieving what I want to achieve?
Ideally a function which took a couple of arguments to determine how
the loops behave would be good, but I can't find a way of doing it.
Whilst its easy to pass the start and end points of the loops, I can
find no way of changing the "i < imax" to be an "i >= 0", so passing
those does not help.

Suggestions welcome.

Dr. David Kirkby.

My real email address can be found at:
http://homepage.ntlworld.com/drkirkby/home-email.jpg
 
Reply With Quote
 
 
 
 
Brett Frankenberger
Guest
Posts: n/a
 
      10-22-2003
In article <(E-Mail Removed)> ,
Dr. David Kirkby <(E-Mail Removed) m> wrote:
>
>Can anyone find a ***neat*** way of doing this in a C function?


for (n=1; n < n_max; n++)
for (k=0; k<4; k++)
for (i1=0; i1 < imax; i1++)
for (j1 = 0; j1 < jmax; j1++) {
i = n & 1 ? i1 : imax - i1;
j = n & 2 ? j1 : jmax - j1;
...
};

Or perhaps:

for (n=1; n < n_max; n++)
for (k=0; k<4; k++)
for (i = n&1 ? 0 : imax; n&1 ? i < imax : i >= 0 ; n&1 ? i++ : i--)
for (j = n&2 ? 0 : jmax; n&2 ? j < imax : j >= 0 ; n&2 ? j++ : j--) {
...
};

-- Brett
 
Reply With Quote
 
 
 
 
Glen Herrmannsfeldt
Guest
Posts: n/a
 
      10-24-2003

"Brett Frankenberger" <(E-Mail Removed)> wrote in message
news:bn4u2o$ice$(E-Mail Removed)...
> In article <(E-Mail Removed)> ,
> Dr. David Kirkby <(E-Mail Removed) m> wrote:
> >
> >Can anyone find a ***neat*** way of doing this in a C function?

>
> for (n=1; n < n_max; n++)
> for (k=0; k<4; k++)
> for (i1=0; i1 < imax; i1++)
> for (j1 = 0; j1 < jmax; j1++) {
> i = n & 1 ? i1 : imax - i1;
> j = n & 2 ? j1 : jmax - j1;
> ...
> };
>
> Or perhaps:
>
> for (n=1; n < n_max; n++)
> for (k=0; k<4; k++)
> for (i = n&1 ? 0 : imax; n&1 ? i < imax : i >= 0 ; n&1 ? i++ : i--)
> for (j = n&2 ? 0 : jmax; n&2 ? j < imax : j >= 0 ; n&2 ? j++ :

j--) {

I think you have some n's where you should have k's, but otherwise...

I would probably use a switch with four sets of loops inside. That would
give the compiler a chance to properly optimize each loop. Otherwise, the
fisst one might optimize better than the second, though the second probably
satisfies the "neat" requirement better.

Just to complain again about the lack of power of the C preprocessor
relative to PL/I, the PL/I preprocessor could expand four loops at compile
time a little easier than C.

-- glen


 
Reply With Quote
 
David Frank
Guest
Posts: n/a
 
      10-25-2003

"Glen Herrmannsfeldt" <(E-Mail Removed)> wrote in message
news:6a1mb.6076$ao4.13422@attbi_s51...
>
> "Brett Frankenberger" <(E-Mail Removed)> wrote in message
> news:bn4u2o$ice$(E-Mail Removed)...
> > In article <(E-Mail Removed)> ,
> > Dr. David Kirkby

<(E-Mail Removed) m> wrote:
> > >
> > >Can anyone find a ***neat*** way of doing this in a C function?

> >
> > for (n=1; n < n_max; n++)
> > for (k=0; k<4; k++)
> > for (i1=0; i1 < imax; i1++)
> > for (j1 = 0; j1 < jmax; j1++) {
> > i = n & 1 ? i1 : imax - i1;
> > j = n & 2 ? j1 : jmax - j1;
> > ...
> > };
> >
> > Or perhaps:
> >
> > for (n=1; n < n_max; n++)
> > for (k=0; k<4; k++)
> > for (i = n&1 ? 0 : imax; n&1 ? i < imax : i >= 0 ; n&1 ? i++

: i--)
> > for (j = n&2 ? 0 : jmax; n&2 ? j < imax : j >= 0 ; n&2 ?

j++ :
> j--) {
>
> I think you have some n's where you should have k's, but

otherwise...
>
> I would probably use a switch with four sets of loops inside. That

would
> give the compiler a chance to properly optimize each loop.

Otherwise, the
> fisst one might optimize better than the second, though the second

probably
> satisfies the "neat" requirement better.
>
> Just to complain again about the lack of power of the C preprocessor
> relative to PL/I, the PL/I preprocessor could expand four loops at

compile
> time a little easier than C.
>
> -- glen
>
>
>


And Fortran will unroll and inline the subroutine code even better
with no preprocessor help..

This problem seems to invite "parallelization" and the
Fortran syntax,

forall (i=1:imax,j=1:jmax) array_stuff

is a invitation for the compiler to generate multi-processor code.

Lacking multi-processing capability, I would put below in my exec,
and call the array stuff with appropriate indices..

! ----------------------
do n = 1,n_max

icase = mod(n-1,4)+1 ! 4 sequential "n cases"

select case (icase)
case (1)
do i = 1,imax
do j = 1,jmax
call array_stuff(i,j)
end do
end do
case (2)
do i = 1,imax
do j = jmax,1,-1
call array_stuff(i,j)
end do
end do
case (3)
do i = imax,1,-1
do j = 1,jmax
call array_stuff(i,j)
end do
end do
case (4)
do i = imax,1,-1
do j = jmax,1,-1
call array_stuff(i,j)
end do
end do
end select
end do


 
Reply With Quote
 
Glen Herrmannsfeldt
Guest
Posts: n/a
 
      10-26-2003

"David Frank" <(E-Mail Removed)> wrote in message
news:hktmb.34803$(E-Mail Removed) ...
>
> "Glen Herrmannsfeldt" <(E-Mail Removed)> wrote in message
> news:6a1mb.6076$ao4.13422@attbi_s51...
> >
> > "Brett Frankenberger" <(E-Mail Removed)> wrote in message
> > news:bn4u2o$ice$(E-Mail Removed)...
> > > In article <(E-Mail Removed)> ,
> > > Dr. David Kirkby

> <(E-Mail Removed) m> wrote:
> > > >
> > > >Can anyone find a ***neat*** way of doing this in a C function?
> > >
> > > for (n=1; n < n_max; n++)
> > > for (k=0; k<4; k++)
> > > for (i1=0; i1 < imax; i1++)
> > > for (j1 = 0; j1 < jmax; j1++) {
> > > i = n & 1 ? i1 : imax - i1;
> > > j = n & 2 ? j1 : jmax - j1;
> > > ...
> > > };
> > >
> > > Or perhaps:
> > >
> > > for (n=1; n < n_max; n++)
> > > for (k=0; k<4; k++)
> > > for (i = n&1 ? 0 : imax; n&1 ? i < imax : i >= 0 ; n&1 ? i++

> : i--)
> > > for (j = n&2 ? 0 : jmax; n&2 ? j < imax : j >= 0 ; n&2 ?

> j++ :
> > j--) {
> >
> > I think you have some n's where you should have k's, but

> otherwise...
> >
> > I would probably use a switch with four sets of loops inside. That

> would
> > give the compiler a chance to properly optimize each loop.

> Otherwise, the
> > fisst one might optimize better than the second, though the second

> probably
> > satisfies the "neat" requirement better.
> >
> > Just to complain again about the lack of power of the C preprocessor
> > relative to PL/I, the PL/I preprocessor could expand four loops at

> compile
> > time a little easier than C.
> >
> > -- glen
> >
> >
> >

>
> And Fortran will unroll and inline the subroutine code even better
> with no preprocessor help..
>
> This problem seems to invite "parallelization" and the
> Fortran syntax,
>
> forall (i=1:imax,j=1:jmax) array_stuff
>
> is a invitation for the compiler to generate multi-processor code.
>
> Lacking multi-processing capability, I would put below in my exec,
> and call the array stuff with appropriate indices..
>
> ! ----------------------
> do n = 1,n_max
>
> icase = mod(n-1,4)+1 ! 4 sequential "n cases"
>
> select case (icase)
> case (1)
> do i = 1,imax
> do j = 1,jmax
> call array_stuff(i,j)
> end do
> end do
> case (2)
> do i = 1,imax
> do j = jmax,1,-1
> call array_stuff(i,j)
> end do
> end do
> case (3)
> do i = imax,1,-1
> do j = 1,jmax
> call array_stuff(i,j)
> end do
> end do
> case (4)
> do i = imax,1,-1
> do j = jmax,1,-1
> call array_stuff(i,j)
> end do
> end do
> end select
> end do


I don't think you are answering the right question.

What the PL/I preprocessor can do is generate the four different
combinations of increment/decrement loops. Well, that would be more
important if the stuff inside the loop were more complicated.

That doesn't have anything to do with parallelization. The original
question didn't say why those four choices were needed.

-- glen


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Reversing Bit Order.. i.e. MSB becomes bit 0, LSB becomes bit 15 benn686@hotmail.com C++ 9 08-22-2007 12:13 AM
Reversing order of words in a given string Kelly B C Programming 2 04-26-2007 02:52 PM
Python 3000 idea: reversing the order of chained assignments Marcin Ciura Python 27 03-22-2007 06:42 PM
Reversing order of quicksort flipflop C Programming 2 05-30-2004 08:54 PM
Reversing order of quicksort flipflop C Programming 3 05-28-2004 04:49 PM



Advertisments