Most optmized code

This is a discussion on Most optmized code within the C Programming forums, part of the General Programming Boards category; Help wanted for writing most optmized "C" code for following arithemntic calculation. y = (x * 63.66667)/128 There is one ...

  1. #1
    Registered User
    Join Date
    Nov 2002
    Posts
    38

    Most optmized code

    Help wanted for writing most optmized "C" code for following arithemntic calculation.

    y = (x * 63.66667)/128

    There is one floating point operation. But this needs to be converted to decimal operation.

    Please let me know..

    Thanks,
    Juganoo

  2. #2
    Registered User Sargnagel's Avatar
    Join Date
    Aug 2002
    Posts
    166
    a first optimization is this:

    y = (x * 63.66667)>>7

    But your compiler may already replace the division by 128 with the right shift operation above.

    btw: what are the data types of x and y?

  3. #3
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    x and y are 32 bit numbers. Floating point operation is not acceptable.

    I have come up with this solution

    y = ( ( x << 6)- ( x/3) )>> 7

    Now it takes. one right shift, one left shift, one division and one substraction.

    Can anybody reduce the number of operations?

    Let me know..

    Juganoo

  4. #4
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    How about this?
    Code:
    y = (x * 191) / 384;

  5. #5
    Registered User Sargnagel's Avatar
    Join Date
    Aug 2002
    Posts
    166
    Have a look at this site:

    http://www.azillionmonkeys.com/qed/adiv.html

    "Integer division ... if the divisor is a constant we can simply use fixed point approximation methods to multiply by the reciprocal"

  6. #6
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    Dave,

    Could you please post your analysis for ur answer.

    I liked that -

  7. #7
    Registered User
    Join Date
    Jan 2003
    Posts
    99
    I have never been able to understand left an right shifts.

  8. #8
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    >Could you please post your analysis for ur answer.
    Not much of an analysis: the fractional part, 0.66667, looked like a familiar fraction, 2/3. So 63.66667, if it were really 63 2/3, could be represented as 191/3. Then (191/3)/128 can be simplified to 191/384.

  9. #9
    Registered User rmullen3's Avatar
    Join Date
    Nov 2001
    Posts
    330

    ~

    y = x * 0.497395859375;

    zoom
    "He who makes a beast of himself, gets rid of the pain of being a man." Dr. Johnson

  10. #10
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Comment #1
    > y = (x * 63.66667)/128
    The difference between this and
    y = (x * 64)/128
    Is about 0.5%

    Put it this way, if y is an integer, then x has to be >= 384 before the real answer (191) becomes different from the approximate answer (192).

    So this simply becomes
    y = x / 2;
    But if you compare the result of y = (x * 63.66667)/128 with the result of y = x / 2, and want them to match, then that 0.5% is critical to the calculation. The x / 2 approximation only produces a match for odd values less than 191 and zero (at least in my little experiment).
    Code:
    #include <stdio.h> 
    
    int main(void) 
    {
       int x, y, z, a = 0, b = 0, c = 0;
       for ( x = 0; x < 110000; ++x )
       {
          z = y = (x * 63.66667) / 128; /* uses floating point */
    
          y = x / 2;
          if ( y == z )
          {
             ++a;
             printf("x = %d, y = x / 2 = %d, z = %d (match)\n", x, y, z);
          }
    
          y = (x * 191) / 384;
          if ( y == z )
          {
             ++b;
          }
          else
          {
             printf("x = %d, y = (x * 191) / 384 = %d, z = %d (doesn't match)\n", x, y, z);
          }
    
          y = ( (x << 6) - (x / 3) ) >> 7;
          if ( y == z )
          {
             ++c;
          }
          else
          {
             printf("x = %d, y = ( (x << 6) - (x / 3) ) >> 7 = %d, z = %d (doesn't match)\n", x, y, z);
          }
       }
       printf("%s accuracy: %d/%d (%f%%)\n", "y = x / 2", a, x, 100.0 * a / x);
       printf("%s accuracy: %d/%d (%f%%)\n", "y = (x * 191) / 384", b, x, 100.0 * b / x);
       printf("%s accuracy: %d/%d (%f%%)\n", "y = ( (x << 6) - (x / 3) ) >> 7", c, x, 100.0 * c / x);
       return 0; 
    }
    With the loop messages removed, the end results I obtained are as follows.
    Code:
    y = x / 2 accuracy: 97/110000 (0.088182%)
    y = (x * 191) / 384 accuracy: 109974/110000 (99.976364%)
    y = ( (x << 6) - (x / 3) ) >> 7 accuracy: 109453/110000 (99.502727%)
    Note that I chose 110000 as the end because y = (x * 191) / 384 matches the result of y = (x * 63.66667) / 128 accurately only up to around 100000. Beyond 100000, the difference between 63.66667 and the fraction 191/384 becomes significant, and the overall accuracy decreases.

    The y = ( (x << 6) - (x / 3) ) >> 7 differs at 2 and and about every 192 thereafter.


    Comment #2
    x and y are 32 bit numbers. Floating point operation is not acceptable.
    y = x * 0.497395859375;
    How exactly does this not use floating point?

  11. #11
    Registered User rmullen3's Avatar
    Join Date
    Nov 2001
    Posts
    330

    ~

    Whoops. Didn't read that he didn't want to use floating point.
    "He who makes a beast of himself, gets rid of the pain of being a man." Dr. Johnson

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Extended ASCII Characters in an RTF Control
    By JustMax in forum C Programming
    Replies: 18
    Last Post: 04-03-2009, 09:20 PM
  2. Enforcing Machine Code Restrictions?
    By SMurf in forum Tech Board
    Replies: 21
    Last Post: 03-30-2009, 08:34 AM
  3. Values changing without reason?
    By subtled in forum C Programming
    Replies: 2
    Last Post: 04-19-2007, 11:20 AM
  4. Interface Question
    By smog890 in forum C Programming
    Replies: 11
    Last Post: 06-03-2002, 06:06 PM
  5. Replies: 0
    Last Post: 02-21-2002, 06:05 PM

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