Rounding up integer without using float, double, or division

Question

Its an embedded platform thats why such restrictions.

original equation: 0.02035*c*c - 2.4038*c

Did this:

int32_t val = 112; // this value is arbitrary
int32_t result = (val*((val * 0x535A8) - 0x2675F70));
result = result>>24;

The precision is still poor. When we multiply val*0x535A8 Is there a way we can further improve the precision by rounding up, but without using any float, double, or division.

Answer 1

The problem is not precision. You're using plenty of bits.

I suspect the problem is that you're comparing two different methods of converting to int. The first is a cast of a double, the second is a truncation by right-shifting.

Converting floating point to integer simply drops the fractional part, leading to a round towards zero; right-shifting does a round down or floor. For positive numbers there's no difference, but for negative numbers the two methods will be 1 off from each other. See an example at http://ideone.com/rkckuy and some background reading at Wikipedia.

Your original code is easy to fix:

int32_t result = (val*((val * 0x535A8) - 0x2675F70));
if (result < 0)
    result += 0xffffff;
result = result>>24;

See the results at http://ideone.com/D0pNPF

You might also just decide that the right shift result is OK as is. The conversion error isn't greater than it is for the other method, just different.

Edit: If you want to do rounding instead of truncation the answer is even easier.

int32_t result = (val*((val * 0x535A8) - 0x2675F70));
result = (result + (1L << 23)) >> 24;

I'm going to join in with some of the others in suggesting that you use a constant expression to replace those magic constants with something that documents how they were derived.

static const int32_t a = (int32_t)(0.02035 * (1L << 24) + 0.5);
static const int32_t b = (int32_t)(2.4038 * (1L << 24) + 0.5);
int32_t result = (val*((val * a) - b));

Answer 2

How about just scaling your constants by 10000. The maximum number you then get is 2035*120*120 - 24038*120 = 26419440, which is far below the 2^31 limit. So maybe there is no need to do real bit-tweaking here.

As noted by Joe Hass, your problem is that you shift your precision bits into the dustbin.

Whether shifting your decimals by 2 or by 10 to the left does actually not matter. Just pretend your decimal point is not behind the last bit but at the shifted position. If you keep computing with the result, shifting by 2 is likely easier to handle. If you just want to output the result, shift by powers of ten as proposed above, convert the digits and insert the decimal point 5 characters from the right.