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
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 ...
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
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
"He who makes a beast of himself, gets rid of the pain of being a man." Dr. Johnson
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).> 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
x and y are 32 bit numbers. Floating point operation is not acceptable.How exactly does this not use floating point?y = x * 0.497395859375;
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