calculating avarage and not letting sum/count to go too high

[Gyiove]

Hello everyone.

Here's a classic way how I would calculate the avarage

double sum = 0.0;
double count = 0.0;
double calculate( double value ) {
sum += value;
count += 1.0;
return sum / count;
}

now imagine me calling this infinite times.
There comes a point there everything goes crazy because sum gets too big and reaches its limits.

How could i calculate avarage so that the variables sum or count would not get too big?


I am talking about the limit, for example unsigned int maximum value is 4294967296, adding one more and it will be 0 instead of 4294967297.

I don't know what the double or flout would do tho.

Any solutions?
Thanks

[helios]

double can represent uniformly spaced integers up to 2^52 - 1. Storing this many doubles would require 2^40 petabytes.
From 2^52 to 2^53 - 1 it can only represent even integers. From 2^53 to 2^54 - 1 it can only represent multiples of 4, and so on up to 2^2048.

[Gyiove]

Okay ... The thing is that i want to calculate avarage with double sized variables and only using 2, sum and count.

Problem is that sum goes way too high over the time.
I somehow need to make sum and count lower so that the return value would not changes and the next calculate function call's return would be the same as without lowering sum/count values.

I am looking for mathematical way.

[helios]

The code you posted is correct. If the result is going haywire then either you have huge outliers or you're passing garbage to the function.

[Gyiove]

Okay, i should be more specific of what i want to do.

I need to calculate avarage error for neural network each time i do the backpropagation.
I calculate the learning speed/momentum based on error avarage.
Also based of error avarage, i know whether to add new neuron or remove one.
It's a bit more complicated but everything relies on error avarage.

The thing is that backpropagation function could be called enough times that sum variable may get too high.

Any ideas of how could i lower the sum variable and count variabes in that way that
everything continues working like i never would't have lowered the sum and count variable?

[helios]

The only way to prevent an overflow when computing an average is by computing a1/n + a2/n + ... an/n instead of (a1 + a2 + ... + an)/n, but this requires knowing in advance how many values you have to average.

Doubles are really hard to overflow, but adding a double to a garbage value will yield a garbage value. Are you absolutely sure that you don't have uninitialized data or some kind of memory bug? Approximately how many values do you expect there to be, and in what range are those values?

[JLBorges]

https://en.wikipedia.org/wiki/Moving_average#Cumulative_moving_average

[aphillips801]

Hi Gyiove, I understand your concern. Potential overflow when calculating the average of a large set of integers is quite a common source of bugs.

When using floating point numbers (as in your example) you don't get overflows, but instead there is a loss of significance. With a very large set of numbers this can be significant.

If you know your worst case you can might be able to choose an appropriate type for the sum. For example, many compilers provide a 64-bit integer type (perhaps called long long or __int64).

However, if you have an indefinite count of numbers to deal with (ie unknown beforehand) you have a problem. I think this is what you were getting at when you mention "infinite times".

In that case I think you need an infinite precision math library. An astonishingly good one for C/C++ is GMP (see http://www.gmplib.org/ ). I recently incorporated it into the calculator embedded in my hex editor (see http://www.hexedit.com ) and was astounded that it could calculate 1000000! (factorial of 1 million) in less than a minute. (BTW 1000000! is an integer with more than a million digits!)

[JLBorges]

Cumulative moving average:

#include <iostream>
#include <string>
#include <random>

int main()
{
    std::mt19937 rng( std::random_device{}() ) ;
    const double minv = 1000.0 ;
    const double maxv = 5000.0 ;
    std::uniform_real_distribution<double> distrib( minv, maxv ) ;
    const long long nvalues = 100'000'000 ;
    const auto nprint = nvalues / 5 ;
    
    double average = 0 ;
    
    for( long long n = 0 ; n < nvalues ; ++n ) 
    {
        const double value = distrib(rng) ;
        // see: https://en.wikipedia.org/wiki/Moving_average#Cumulative_moving_average
        average +=  ( value - average ) / (n+1) ;
        if( n % nprint == (nprint-1) ) std::cout << std::fixed << "after " << n+1 << " values, moving average is: " << average << '\n' ;
    }
    
    std::cout << "\nexpected value: " << (minv+maxv)/2 << "  computed average: " << average << '\n' ;
}

after 20000000 values, moving average is: 2999.985586
after 40000000 values, moving average is: 2999.888527
after 60000000 values, moving average is: 3000.001183
after 80000000 values, moving average is: 3000.069204
after 100000000 values, moving average is: 3000.063402

expected value: 3000.000000  computed average: 3000.063402

http://coliru.stacked-crooked.com/a/df32cf69751477ca

[JLBorges]

To estimate the error in computing the average as a moving average:

#include <iostream>
#include <string>
#include <random>
#include <boost/multiprecision/cpp_bin_float.hpp>
#include <limits>
#include <cmath>

int main()
{
    std::mt19937 rng( std::random_device{}() ) ;
    
    /////////////////// replace with the actual distribution of values //////////// 
    const double minv = 0.0 ;
    const double maxv = 1.0e14 ;
    std::uniform_real_distribution<double> distrib( minv, maxv ) ;
    ////////////////////////////////////////////////////////////////////////////
    
    const long long nvalues = 4'000'000 ;

    double moving_average = 0 ;
    using float_100 = boost::multiprecision::cpp_bin_float_100 ;
    float_100 sum = 0 ;
    std::cout << "float_100 - size: " << sizeof(float_100) << " bytes, decimal digits: " << std::numeric_limits<float_100>::digits10 << '\n'
              << "   double - size: " << sizeof(double) << " bytes, decimal digits: " << std::numeric_limits<double>::digits10 << "\n\n" ;

    for( long long n = 0 ; n < nvalues ; ++n )
    {
        const double value = distrib(rng) ;
        moving_average +=  ( value - moving_average ) / (n+1) ;
        sum += value ;
    }

    const float_100 average_100 = sum / nvalues ;
    const double diff = std::abs( double(average_100) - moving_average ) ;

    std::cout << std::fixed
              << "    sum (100 decimal digits internal precision): " << sum << '\n'
              << "average (100 decimal digits internal precision): " << average_100 << '\n'
              << "              moving average (native precision): " << moving_average << '\n'
              << "                                           diff: " << diff  << " (" << diff * 100.0 / average_100 << "%)\n" ;
}

float_100 - size: 80 bytes, decimal digits: 100
   double - size: 8 bytes, decimal digits: 15

    sum (100 decimal digits internal precision): 200077974452408359971.622596
average (100 decimal digits internal precision): 50019493613102.089993
              moving average (native precision): 50019493613101.640625
                                           diff: 0.453125 (0.000000%)

http://coliru.stacked-crooked.com/a/917d15036d96bedd