Thread: 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

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?

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

How about this?

Code:

y = (x * 191) / 384;

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"

Dave,

Could you please post your analysis for ur answer.

I liked that -

I have never been able to understand left an right shifts.

>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.

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?