Optimisation

[weever]

Hi all, I'm new so here's my first question:

I have an array arr[i*YSIZE + j]

i and j increment in a for loop and YSIZE could be any integer value.

What I'd like to know is how you optimise the array so that you get rid of the multiplication "*". Apparently it is possible but I don't know how to do it.

Please help, this problem has been bugging me for a while now!

Thank you all,
Weever~

[Salem]

> I have an array arr[i*YSIZE + j]

Instead of i++ in your for loop, do i+=YSIZE

Then this becomes
arr[i + j]

[weever]

Thanks for your help, but I'd still have to times "*" the i which is now YSIZE by the original i, if you get what I mean.

Basically what you put was arr[YSIZE + j] and lost the "i *" part. Thanks for trying.

weever~

[Salem]

*shakes head*

#include <stdio.h>

#define YSIZE 5

int main ( ) {
  int i, j, lim;

  for ( i = 0 ; i < 3 ; i++ ) {
    for ( j = 0 ; j < 5 ; j++ ) {
      int pos = i * YSIZE + j;
      printf( "i=%d, j=%d, pos=%d\n", i, j, pos );
    }
  }

  lim = 3*YSIZE;
  for ( i = 0 ; i < lim ; i+=YSIZE ) {
    for ( j = 0 ; j < 5 ; j++ ) {
      int pos = i + j;
      printf( "i=%d, j=%d, pos=%d\n", i, j, pos );
    }
  }

  return 0;
}

[VirtualAce]

Only way to optimize it further is to do shifts to perform the mult instead of *.

y<<6+x

But your array width must be a power of 2 in order for it to work.
This is essentially a mult but it is slightly faster

According to Salem, most compilers will take your y*XSIZE+x or y*YSIZE+x and try to convert it to shifts instead of a mult.

XSIZE and YSIZE depends on whether you are using row ordering or column ordering - I forget the technical names for both approaches

[VirtualAce]

You should put shifts in parentheses or you might not get the results you want.


(y<<6)+x

((y+1)<<6)+x

[weever]

Thanx to both of you for that, and sorry to Salem, I didn't relise you meant that there was still a multiplication just its taken out of the loop.

I'm still not sure if I've got all the info I need on bit shifting so keep watching this space

Thanx to all!!!
weever~