Rotate array problem

Discussion in 'Programmer's Corner' started by Art, Jul 7, 2009.

  1. Art

    Thread Starter Distinguished Member

    Sep 10, 2007
    785
    61
    Hi Guys,
    This is a function that can rotate a 256 element array:

    Problem is it rotates in the wrong direction.
    Anyone want to have a crack at the other direction?
    No matter what I try I break it.

    I realise I can just replace the 1 for 255 and use this for the same effect
    as the other direction, but that takes too much time for the application.
    Cheers, Art.
     
  2. THE_RB

    AAC Fanatic!

    Feb 11, 2008
    5,435
    1,305
    Here are 2 simple systems, they circular rotate the data either way. The rotation has been kept as simple as possible and the last array element
    is manually held in dat and restored at the end. There's plenty of other
    ways to do it, but these are basically a mirror image of each other so
    you might find them easy to understand.

    Code ( (Unknown Language)):
    1.  
    2. // rotates array data right (up)
    3. unsigned char i;
    4. unsigned char dat;
    5.  
    6. i=0;
    7. dat = colours[0];
    8. while(--i)
    9. {
    10.     colours[i+1] = colours[i];
    11. }
    12. colours[1] = dat;
    13.  
    14.  
    15. // rotates array data left (down)
    16. unsigned char i;
    17. unsigned char dat;
    18.  
    19. i=0;
    20. dat = colours[1];
    21. while(++i)
    22. {
    23.     colours[i] = colours[i+1];
    24. }
    25. colours[0] = dat;
    26. [/i][/i]
     
    Last edited: Jul 15, 2009
  3. RiJoRI

    Well-Known Member

    Aug 15, 2007
    536
    26
    Some compilers will not do this as desired:
    Code ( (Unknown Language)):
    1. i=0;
    2. while(i--)
    They will (should? ) test i before decrementing it -- which is, after all, what you are telling it to do. The code also assumes a char is an 8-bit value.

    A better way would be
    Code ( (Unknown Language)):
    1. for(i = 0; i < 256; i++)
    This way it is quite plain what you are trying to do.

    And don't forget, marketing is going to want to change the colour array to 300 entries in a few years. Searching for all occurrences of 256 is going to be A Real Pain.

    --Rich
    (Burnt by C)
     
  4. Mark44

    Well-Known Member

    Nov 26, 2007
    626
    1
    Neither Rich nor THE_RB mentioned this, but your outer loop executes only once. Surely you didn't intend that. Here is your code, unchanged except that I formatted it for better readability.
    Code ( (Unknown Language)):
    1.  
    2. int ii, jj;
    3.  
    4. for (ii = 1; ii <=1; ii++)
    5. {
    6.     for (jj = 256-1; jj > 0; jj--)
    7.     {
    8.         colours[jj-1] = colours[jj-1] + colours[jj];
    9.         colours[jj] = colours[jj-1] - colours[jj];
    10.         colours[jj-1] = colours[jj-1] - colours[jj];
    11.     }
    12. }
    13.  
     
  5. Art

    Thread Starter Distinguished Member

    Sep 10, 2007
    785
    61
    Thanks for the replies :)
    Yeah, the constant 1 can be a variable that determines how many places to shift.
     
  6. THE_RB

    AAC Fanatic!

    Feb 11, 2008
    5,435
    1,305
    A good point, but I believe you are wrong. In C the compiler will perform the expression first, before evaluating it. That is if the compiler conforms to C rules which it should.

    Yeah I hear you there, a for() expression is the standard way to do it. But the while() expression compiles to a lot smaller and faster code, something i've been made very aware of lately since my C coding these days is mainly for low level PIC micros where every uS counts.

    When the original poster mentioned "takes too much time for the application" I assumed execution time was critical and stripped the code to the very fastest and minimal code I could think up in 2 minutes. ;)
     
  7. RiJoRI

    Well-Known Member

    Aug 15, 2007
    536
    26
    From: http://docs.hp.com/en/B3901-90007/ch05s09.html

    As to the for/while question, I usually check the output of the compiler to see which, if either, is faster. A possible reason for sluggishness is the arithmetic contortions the OP is going through in the loop. I'd look to see if using pointers was better, or maybe strcpy().

    --Rich
     
  8. Mark44

    Well-Known Member

    Nov 26, 2007
    626
    1
    Rich is right on the mark here. Not to pile on here, but for the post-decrement expression i--, the compiler generates code that evaluates the expression (an expression doesn't get performed), and after that decrements the variable.
     
  9. SgtWookie

    Expert

    Jul 17, 2007
    22,182
    1,728
  10. THE_RB

    AAC Fanatic!

    Feb 11, 2008
    5,435
    1,305
    Whoops my apologies Rich, you are right I should have typed;

    while(--i)
    and
    while(++i)
    (I fixed it now with an edit)

    I do understand pre and post incrementing but that typo slipped past me, which was why I was defending the fact that it performs the ++i increment expression first before being evaluated by the while() expression.

    Nice link Sgtwookie. Still the best way to handle a circular array is still to leave the data where it is and reference it by a pointer. How often do you actually NEED to rotate the data in a circular array?
     
Loading...