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
Printable View
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.
y = x * 0.497395859375;
zoom
Comment #1
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).Quote:
> 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;
With the loop messages removed, the end results I obtained are as follows.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;
}
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.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%)
The y = ( (x << 6) - (x / 3) ) >> 7 differs at 2 and and about every 192 thereafter.
Comment #2
Quote:
x and y are 32 bit numbers. Floating point operation is not acceptable.
How exactly does this not use floating point?Quote:
y = x * 0.497395859375;
Whoops. Didn't read that he didn't want to use floating point.