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

Thanks,
Juganoo

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

Code:
`y = (x * 191) / 384;`

5. Have a look at this site:

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

6. Dave,

I liked that -

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

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

y = x * 0.497395859375;

zoom

10. Comment #1
> y = (x * 63.66667)/128
The difference between this and
y = (x * 64)/128

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

Whoops. Didn't read that he didn't want to use floating point.