Home > math, python > Calculating the average incrementally

Calculating the average incrementally

This entry is based on Sándor Norbert’s post on Incremental average calculation.

I have a large list with very large numbers and I want to calculate their average. However, I’m afraid there would be an overflow while summing up the elements.

The traditional average computation first calculates the sum of the elements and then this sum is divided by the number of elements. However, the average can be calculated incrementally too, i.e. you take the 1st element and you calculate its average, then take the 2nd element and update the average, and so on. When you process the last element, you have the average of the whole list. Let’s see it mathematically.

Recall the traditional average:

Now let’s see the incremental formula:

That is:

Thus, the average up to i elements:

The algorithm in Python:

def inc_avg(li):
    """Calculate the average incrementally.
    Input: a list.
    Output: average of the list."""
    left = 0
    right = len(li)-1

    avg = li[left]
    left += 1

    while left <= right:
        curr = left + 1
        avg += (li[left] - avg) / float(curr)
        left += 1

    return avg

Experimental results
TODO: compare the runtime of plain average with this incremental solution.

Categories: math, python Tags: ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: