CODEWITHSUNDEEP
c++mathoverflow
user16269793
user16269793

Reputation:

Overflow When Calculating Average?

Given 2 integer numbers we can calculate their average like this:

return (a+b)/2;

which isn't safe since (a+b) can cause overflow (Side Note: can someone tell me the correct term for this case maybe memory overflow?)

So we write:

return a+(b-a)/2;

can the same trick be implemented over n numbers and how?

Upvotes: 2

Views: 2002

Answers (2)

Ranoiaetep
Ranoiaetep

Reputation: 6647

One way of getting average number for multiple numbers is to find the Cumulative Moving Average, or CMA:

Your code a + (b - a) / 2 can also be derived from this equation for n + 1 == 2.

Translating above equation to code, you would get something similar to:

std::vector<int> vec{10, 5, 8, 3, 2, 8}; // average is 6

double average = 0.0;

for(auto n = 0; n < vec.size(); ++n)
{
    average += (vec[n] - average) / (n + 1);
}

std::cout << average; // prints 6

Alternatively, you can also use the std::accumulate:

std::cout << std::accumulate(vec.begin(), vec.end(), 0.0, 
                             [n = 0](auto cma, auto i) mutable {
                                 return cma + (i - cma) / ++n;
                             });

Do note any time you are using floating division can result into imprecise result, especially when you attempt to do that for numerous times. For more regarding impreciseness, you can look at: Is floating point math broken?

Upvotes: 2

eerorika
eerorika

Reputation: 238401

Note that there are several different averages. I assume that you're asking about the arithmetic mean.

overflow (Side Note: can someone tell me the correct term for this case maybe memory overflow?)

The correct term is arithmetic overflow, or just overflow. Not memory overflow.

a+(b-a)/2;

b-a can also overflow. This isn't quite as easy to solve as it may seem.

Standard library has a function template to do this correctly without overflow: std::midpoint.

I checked an implementation of std::midpoint, and they do what you suggested for integers, except the operands are first converted to the corresponding unsigned type. Then the result is converted back. A mathematician may explain how that works, but I guess that it has something to do with the magic of modular arithmetic.

For floats, they do a / 2 + b / 2 (if the inputs are normal).

can the same trick be implemented over n numbers and how?

Simplest solution that works with all inputs without overflow and without imprecision is probably to use arbitrary precision arithmetic.

Upvotes: 4

Related Questions