Running Average

From arrizza.org wiki

Revision as of 21:19, 20 June 2020 by Jarrizza1 (talk | contribs) (Git repository)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search
Previous ⇦ One Millisecond Loop Algorithms ⇫ Up Fast Integer Rounding ⇨ Next

Overview

It is sometimes necessary to keep track of an average for a list of numbers that are input only one at a time.

Git repository

https://bitbucket.org/arrizza/algorithms/src/master/average.cpp

git clone git@bitbucket.org:arrizza/algorithms.git

Using the full list

The average of a set of numbers is the the sum of the numbers divided by the number of items.

In code this looks like:

#include <iostream>

#define N 5
int list[N];

void use_full_list(int* list)
  {

  int      sum = 0;
  for (int i   = 0; i < N; ++i)
    {
    sum += list[i];
    }

  double average = (double) sum / N;

  printf("%-15s: sum: %3d N: %3d average: %.2f\n", "full list", sum, N, average);
  }

int main(void)
  {
  list[0] = 1;
  list[1] = 2;
  list[2] = 4;
  list[3] = 3;
  list[4] = 2;

  use_full_list(list);

  return 0;
  }

which generates this output:

full list      : sum:  12 N:   5 average: 2.40

Running Average

But this requires the full set of numbers to calculate. What if we didn't want to store the full set of numbers?

void one_at_a_time(int val, int& num_elems, int& sum, double& average)
  {
  num_elems += 1;
  sum += val;
  average = (double) sum / num_elems;
  printf("%-15s: sum: %3d N: %3d average: %.2f\n", "one at a time", sum, num_elems, average);
  }

  // and in main()
  int      num_elems = 0;
  int      sum       = 0;
  double   average   = 0.0;
  for (int i         = 0; i < N; ++i)
    {
    one_at_a_time(list[i], num_elems, sum, average);
    }

gives output:

one at a time  : sum:   1 N:   1 average: 1.00
one at a time  : sum:   3 N:   2 average: 1.50
one at a time  : sum:   7 N:   3 average: 2.33
one at a time  : sum:  10 N:   4 average: 2.50
one at a time  : sum:  12 N:   5 average: 2.40

In other words, we get the same final result but we can calculate the average on the fly.

In math:

Storing the Average

But notice the sum in the output above, it keeps going up 1, 3, 7 etc.. It may be possible that we overflow the variable sum.

void only_average(int val, int& num_elems, double& average)
  {
  double sum = average * num_elems;
  sum += val;
  num_elems += 1;
  average    = sum / num_elems;
  printf("%-15s: sum: %5.2f N: %3d average: %5.2f\n", "only average", sum, num_elems, average);
  }

// and in main()
  int      num_elems2 = 0;
  double   average2   = 0.0;
  for (int i          = 0; i < N; ++i)
    {
    only_average(list[i], num_elems2, average2);
    }

The output is:

only average   : sum:  1.00 N:   1 average:  1.00
only average   : sum:  3.00 N:   2 average:  1.50
only average   : sum:  7.00 N:   3 average:  2.33
only average   : sum: 10.00 N:   4 average:  2.50
only average   : sum: 12.00 N:   5 average:  2.40

Again, we get the same final average but this time we only store a couple of variables.

In math:

Caveats

Note that the line

 double sum = average * num_elems;

can still overflow.

And also note that this may not be exactly equal to since it is finite arithmetic,

Personal tools