Optimisation

This is a discussion on Optimisation within the C Programming forums, part of the General Programming Boards category; Hi all, I'm new so here's my first question: I have an array arr[i*YSIZE + j] i and j increment ...

  1. #1
    Registered User
    Join Date
    Jan 2002
    Posts
    7

    Lightbulb Optimisation

    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~

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,546
    > I have an array arr[i*YSIZE + j]

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

    Then this becomes
    arr[i + j]

  3. #3
    Registered User
    Join Date
    Jan 2002
    Posts
    7
    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~

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,546
    *shakes head*

    Code:
    #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;
    }

  5. #5
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    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

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,596
    You should put shifts in parentheses or you might not get the results you want.


    (y<<6)+x

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

  7. #7
    Registered User
    Join Date
    Jan 2002
    Posts
    7
    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~

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Hello!a simple optimisation required!
    By chottachatri in forum C Programming
    Replies: 10
    Last Post: 10-19-2008, 07:06 AM
  2. passing std::vector and optimisation
    By l2u in forum C++ Programming
    Replies: 10
    Last Post: 07-03-2008, 11:01 AM
  3. Benchmarking and Optimisation Q's
    By studiesrule in forum C++ Programming
    Replies: 11
    Last Post: 10-19-2006, 07:57 AM
  4. Optimisation of reading from file
    By bc2005 in forum C Programming
    Replies: 2
    Last Post: 01-15-2006, 04:26 AM
  5. Optimisation
    By EvenFlow in forum A Brief History of Cprogramming.com
    Replies: 5
    Last Post: 10-29-2001, 09:14 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21