How can I preserve the order of multiplications and divisions?

Question

On my 32 bit embedded C++ application, I need to perform the following computation:

calc(int milliVolts, int ticks) {
  return milliVolts * 32767 * 65536 / 1000 / ticks;
}

Now, since an int on my platform has 32 bits and milliVolts has a range of [-1000:1000], the milliVolts * 32767 * 65536 part is could cause an integer overflow. To avoid this, I have split the factor 65536 into 1024, 32 and to and reordered as follows:

calc(int milliVolts, int ticks) {
  return milliVolts*32767*32/1000*1024/ticks*2;
}

This way, as long as the order of multiplications and divisions is preserved by the compiler, the function will compute correctly.

Kerninghan and Ritchie state in section 2.12 of "The C programming language" (I don't have a copy of the C++ standard handy):

C, like most languages does not specify the order in which the operands of an operator are evaluated.

If I understand this correctly, the compiler is free to change my carefully chosen expression into something that will not work as intended.

How can I write my function in such a way that it is guaranteed to work?

EDIT: Several answers below suggest using floating point calculations to avoid this issue. This is not an option because the code is running on a CPU that does not have floating point operations. Furthermore the calculation is in the hard realtime part of my application, so the speed penalty of using emulated floating point is too big.

CONCLUSION: With the help of Merdad's answer and Matt McNabb's comment, I managed to find the relevant section in K&R, section A7 where it says:

The precedence and associativity of operators is fully specified, but the order of evaluation of expressions is, with certain exceptions, undefined, even if subexpressions involve side effects. That is, unless the definition of an operator guarantees ths its operands are evaluated in a particular order, the implementation is free to evaluate operands in any order, or even to interleave their evaluation. However, each operator combines the values produced by its operands in a way compatible with the parsing of the expressions in which it appears. This rule revokes the previous freedom to reorder expressions with operators that are matematically commutative and associative, but can fail to be computationally associative. The change affects only floating-point computations near the limits of their accuracy, and situations where overflow os possible.

So Merdad is right: There is nothing to worry about.

Answer 1

Actually:

You (and the others) are misunderstanding what is being said. There is no problem here.

They're saying if you have f(x) + g(y), there is no guarantee that f(x) is evaluated before g(y) (or vice-versa).

But if you have

milliVolts * 32767 * 32 / 1000 * 1024 / ticks * 2

it is automatically interpreted as

(((((milliVolts * 32767) * 32) / 1000) * 1024) / ticks) * 2

which means evaluating the left- and right-hand sides of any operator out of order will not result in any problem, since all the expressions to the right-hand side of an operator are either variables or numbers, in either case of which the evaluation of the right-hand side is a no-op (no side-effects, contrary to a function call).

Thus there is nothing to be worried about.

Answer 2

(This is more of a comment, but was too long to fit in a comments field)

---

"I will use parentheses. Even just to make the code clearer."

Yes, yes and another yes please. While it has been shown that your expression is unambiguous to the compiler, it may still cause confusion in the eyes of the casual reader. I know some people can remember all the precedence rules, but I frequently find myself having to look up this sort of thing. Added parentheses will go a long way to make it clear to the reader.

But most importantly, add a comment explaining exactly why you are having to perform your calculation in this manner. This is exactly the kind of situation where a well-meaning future maintainer comes in and tries to "simplify" your code. A well-placed comment would help fend off such unwanted refactorizations.

Answer 3

My answer would be to cast milliVolts and ticks to int64_t and perform the calculations. Then assert if the results can be stored in the int.

EDIT: datahaki suggest to use floating point values in the calculation. This can prove useful because you are most likely end up calculating with fractions.

Answer 4

You're always going to have a certain round-off error, I think that needs no explanation. So the strategy is to try to minimize the error as much as possible, taking into account that we do not know a-priory the values of millivolt and ticks.

I suggest to divide the calculation in two stages. First, grouping your constants we have: 32767 * 65536 / 1000 = 2147418.112 = 2147418, with an error of 0.112, which is only 1 part in 20 millions, approximately.

So declare a const int:

const int factor = 2147418;

Now, milivolts is in the [-1000,1000] range and ticks in the [1,1024] range. If we calculate millivolts / ticks, we can have large errors; consider for example the situation:

millivolts=1;
ticks=1024;
intermediate = millivolts/ticks = 0;
result = intermediate * factor = 0; /// Big error, as result should be 2097

So I suggest the following:

int intermediate = factor * millivolt;
int result = intermediate / ticks;

This way, in the worst case (millivolt=1000) intermediate fits in a 32-bit integer, which, lacking any information to the contrary, I will assume you can use.