Signed division with unsigned numerator

I'm trying to calculate a rolling average, and to try and get and optimize a bit, I've simplified the calculation so there is only one division. When the value is decreasing, there is a point where the current value is lowered to less than the average. At this point the average jumps. I imagine this is because the division is unsigned, and my numerator's sign bit is interpreted as a massive unsigned number. I am just not sure where I need to cast unsigned to insure this problem doesn't reappear.

unsigned int AverageUsage;
unsigned int TotalUsage;
unsigned int incCount;

    AverageUsage = (TotalUsage - AverageUsage)/++incCo开发者_开发知识库unt + AverageUsage;

AverageUsage will always be positive, but when TotalUsage drops below AverageUsage, I'm not sure what to expect with the division

    AverageUsage = (signed int)(TotalUsage - AverageUsage)/++incCount + AverageUsage;

Will set the numerator to signed, but I am not sure how the division will occur.

    AverageUsage =  (signed int)((signed int)(TotalUsage - AverageUsage)/++incCount) + AverageUsage;

Should work (I can guarantee the result of this full operation will never be negative), but I am worried about cases when incCount reaches a value that 'looks' negative.

Is there a simple solution to this that hopefully:

• Doesn't need an if statement
• Doesn't require QWORDs

Thanks!

The general rule of C binary ops (including division) is that the operands will both be converted to the same type, which is one of: int, unsigned int, long, unsigned long, intmax_t, uintmax_t, float, double, long double. If both operands are of types in that list, they'll both be converted to the later one. If neither is, they'll both be converted to int

So in your example:

AverageUsage = (signed int)(TotalUsage - AverageUsage)/++incCount + AverageUsage

if incCount is unsigned int, then your cast has no effect -- the subtract will be converted to signed int and then right back to unisgned int and an unsigned division will be done. If you want a signed division, you'll need:

AverageUsage = (int)(TotalUsage - AverageUsage)/(int)++incCount + AverageUsage

which as you note may get you into trouble if incCount exceeds INT_MAX.

In general, processor instructions for division only specify one type, which is used for both operands. When there is a special instruction for division with differing types, its usually for a larger (double width) dividend, not a different signedness.

You have 2 options.

Use Floating Point Math

I think you want to do this to get a proper average anyway.

There is no such thing as a mixed floating/integer divide. So, both numerator and denominator will be converted to a floating point.

Whether the numerator or denominator is signed or unsigned then doesn't matter. There is no such thing as unsigned floating point. The denominator incCount will be converted to a floating point and full floating point division will be done.

Use Integer division and handle the special cases

If for some reason you want to stay with integer division, then both the numerator and denominator have to be the same signed/unsigned type.

Both Numerator/Denominator are signed

incCount will be converted to a signed number. If it is too large then it will look like a negative number and your answer will be wrong. You have to test for this overflow.

Both Numerator/Denominator are unsigned

You have to make the numerator unsigned and use a if () statement to handle the two cases: TotalUsage < AverageUsage and TotalUsage > AverageUsage. Here incCount can use the full range of integer bits since it will be treated as an unsigned number.

Note of course that this is not a standard average. A standard average would be:

Averageusage = TotalUsage / ++incCount

Assuming (ideally) that incCount is some useful periodically increasing value (like seconds).

A decaying average is typically implemented more like: http://donlehmanjr.com/Science/03%20Decay%20Ave/032.htm which if I have translated correctly is:

AverageUsage = TotalUsage / (incCount+1) + incCount/(incCount+1) * AverageUsage;
incCount++;

As Himadri mentioned, these should probably be done in floating point arithmetic.

If it is foreseeable and valid for TotalUsage < AverageUsage, then it is entirely inappropriate for these variables to be of unsigned type. TotalUsage < AverageUsage would imply that AverageUsage could then be negative (which would be the result if TotalUsage < AverageUsage. If the data being 'averaged' is never negative, then it is arithmetically impossible for TotalUsage < AverageUsage to be true.

If TotalUsage < AverageUsage is not valid, then for it to be true would indicate an error in your code or an arithmetic overflow. You might guard against that possibility with an assert; perhaps one implemented as a macro that is removed in a release build. If the assert occurs then either the input data was invalid, or an overflow occurred, in the latter case the data type is too small, and either a long long, unsigned long long, or a double would be appropriate.

Even with casting, if TotalUsage < AverageUsage is true then the result of the expression is arithmetically negative, but ultimately assigned to an unsigned type, so the result will still be incorrect.

The ultimate conclusion then is either that TotalUsage < AverageUsage can never be true, or your data has inappropriate type. The solution is almost certainly not any kind of type cast.

My advice is generally to always use a signed type for variables on which arithmetic will be performed. This is because the language semantics of mixed signed/unsigned arithmetic are somewhat arcane and easily misunderstood, and because intermediate operations may generate otherwise negative values. Even if a negative value for the variable is semantically meaningless, I would still advocate the use of signed types in all cases where the positive range of such a type remains sufficient to avoid overflow, and where it is not sufficient. to use a larger type where possible rather than resort to an unsigned type of the same size. Further, where arithmetic operations on unsigned types is required, then all operands should be unsigned (including literals), and no intermediate operation should result under or overflow.

Do you truly /need/ a rolling-average, or can you use some other low-pass filter? A single-pole (sometimes called an "alpha") filter might suit you:

new_output = alpha * previous_output + (1-alpha)*new_input;
previous_output = new_output;

where alpha is between 0 and 0.9999....

The closer alpha is to 1, the "slower" the filter is

You can do this in floating point for ease, or in integers quite straightforwardly.