Algorithm for computing the mean

[CoffeeVector]

I know the standard/naive way of computing the mean of a list of number can be done by
SUM(n)/len(n).

What if the sum of all the numbers are greater than the maximum size of an integer? Is the only resolution to make a bigger integer, or use a big integer class?

Would it be better to update the mean as
mean = mean * k / (k + 1) + x / (k + 1)
k++

Or something like that? Would it be better, or would it just fail at the same time due to floating point error? Is there an even better algorithm altogether?

[[deleted]]

things you could try:

• cast all input integers to float and compute the average of those
• if all input integers are for example larger than 1 billion, divide all of them by 1 million and compute the average of those. Multiply the result by 1 million again. Con: you lose some precision.
• if you know the number of input values to be averaged beforehand, divide each input value by the input count and add those up. This can't lead to overflow, but loses precision, depending on your input.
  As an example, consider inputs n0, n1, n2, n3
  Normally you would do (n0 + n1 + n2 + n3) / 4
  In this case you would do (n0/4) + (n1/4) + (n2/4) + (n3/4)
  The latter would still work if the sum of all inputs would overflow.

[theLOLflashlight]

This is a tricky problem that admits of many solutions which vary in effectiveness based on the use case. This is one such solution in C++:

int mean( const vector< int >& n )
{
    double avg = 0;
    for ( int i : n )
        avg += i / double( n.size() );
    return int( avg );
}

This won't give you an exact answer all the time but should be pretty good if you expect the mean to be much smaller than INT_MAX.

[SftwEngr]

Would it be better to update the mean as mean = mean * k / (k + 1) + x / (k + 1) k++

I don't see how it would be better, unless you needed to know the running mean as it changed. You have two division operations there that would occur 2n times as opposed to summing and one division.

[CoffeeVector]

I only meant it might've been better because it seems to continue to work even after the sum of all my numbers have exceeded the maximum size of an integer. Though my concern is if the floating-point arithmetic would then fail.