How do I find the average in a LARGE set of numbers?

Question

I have a large set of numbers, probably in the multiple gigabytes range. First issue is that I can't store all of these in memory. Second is that any attempt at addition of these will result in an overflow. I was thinking of using more of a rolling average, but it needs to be accurate. Any ideas?

These are all floating point numbers.

This is not read from a database, it is a CSV file collected from multiple sources. It has to be accurate as it is stored as parts of a second (e.g; 0.293482888929) and a rolling average can be the difference between .2 and .3

It is a set of #'s representing how long users took to respond to certain form actions. For example when showing a messagebox, how long did it take them to press OK or Cancel. The data was sent to me stored as seconds.portions of a second; 1.2347 seconds for example. Converting it to milliseconds and I overflow int, long, etc.. rather quickly. Even if I don't convert it, I still overflow it rather quickly. I guess the one answer below is correct, that maybe I don't have to be 100% accurate, just look within a certain range inside of a sepcific StdDev and I would be close enough.

Answer 1

Integers or floats?

If they're integers, you need to accumulate a frequency distribution by reading the numbers and recording how many of each value you see. That can be averaged easily.

For floating point, this is a bit of a problem. Given the overall range of the floats, and the actual distribution, you have to work out a bin-size that preserves the accuracy you want without preserving all of the numbers.

---

Edit

First, you need to sample your data to get a mean and a standard deviation. A few thousand points should be good enough.

Then, you need to determine a respectable range. Folks pick things like ±6σ (standard deviations) around the mean. You'll divide this range into as many buckets as you can stand.

In effect, the number of buckets determines the number of significant digits in your average. So, pick 10,000 or 100,000 buckets to get 4 or 5 digits of precision. Since it's a measurement, odds are good that your measurements only have two or three digits.

---

Edit

What you'll discover is that the mean of your initial sample is very close to the mean of any other sample. And any sample mean is close to the population mean. You'll note that most (but not all) of your means are with 1 standard deviation of each other.

You should find that your measurement errors and inaccuracies are larger than your standard deviation.

This means that a sample mean is as useful as a population mean.

Answer 2

depending on the range of numbers it might be a good idea to have an array where the subscript is your number and the value is the quantity of that number, you could then do your calculation from this

Answer 3

You can sample randomly from your set ("population") to get an average ("mean"). The accuracy will be determined by how much your samples vary (as determined by "standard deviation" or variance).

The advantage is that you have billions of observations, and you only have to sample a fraction of them to get a decent accuracy or the "confidence range" of your choice. If the conditions are right, this cuts down the amount of work you will be doing.

Here's a numerical library for C# that includes a random sequence generator. Just make a random sequence of numbers that reference indices in your array of elements (from 1 to x, the number of elements in your array). Dereference to get the values, and then calculate your mean and standard deviation.

If you want to test the distribution of your data, consider using the Chi-Squared Fit test or the K-S test, which you'll find in many spreadsheet and statistical packages (e.g., R). That will help confirm whether this approach is usable or not.

Answer 4

Wouldn't a rolling average be as accurate as anything else (discounting rounding errors, I mean)? It might be kind of slow because of all the dividing.

You could group batches of numbers and average them recursively. Like average 100 numbers 100 times, then average the result. This would be less thrashing and mostly addition.

In fact, if you added 256 or 512 at once you might be able to bit-shift the result by either 8 or 9, (I believe you could do this in a double by simply changing the floating point mantissa)--this would make your program extremely quick and it could be written recursively in just a few lines of code (not counting the unsafe operation of the mantissa shift).

Perhaps dividing by 256 would already use this optimization? I may have to speed test dividing by 255 vs 256 and see if there is some massive improvement. I'm guessing not.

Answer 5

If the numbers are int's, accumulate the total in a long. If the numbers are long's ... what language are you using? In Java you could accumulate the total in a BigInteger, which is an integer which will grow as large as it needs to be. You could always write your own class to reproduce this functionality. The gist of it is just to make an array of integers to hold each "big number". When you add two numbers, loop through starting with the low-order value. If the result of the addition sets the high order bit, clear this bit and carry the one to the next column.

Another option would be to find the average of, say, 1000 numbers at a time. Hold these intermediate results, then when you're done average them all together.

Answer 6

You could break the data into sets of, say, 1000 numbers, average these, and then average the averages.

Answer 7

Why is a sum of floating point numbers overflowing? In order for that to happen, you would need to have values near the max float value, which sounds odd.

If you were dealing with integers I'd suggest using a BigInteger, or breaking the set into multiple subsets, recursively averaging the subsets, then averaging the averages.

If you're dealing with floats, it gets a bit weird. A rolling average could become very inaccurate. I suggest using a rolling average which is only updated when you hit an overflow exception or the end of the set. So effectively dividing the set into non-overflowing sets.

Answer 8

Two ideas from me:

• If the numbers are ints, use an arbitrary precision library like IntX - this could be too slow, though
• If the numbers are floats and you know the total amount, you can divide each entry by that number and add up the result. If you use double, the precision should be sufficient.

Answer 9

Here's one way to do it in pseudocode:

average=first
count=1
while more:
  count+=1
  diff=next-average
  average+=diff/count
return average

Answer 10

You mean of 32-bit and 64-bit numbers. But why not just use a proper Rational Big Num library? If you have so much data and you want an exact mean, then just code it.

class RationalBignum {
    public Bignum Numerator { get; set; }
    public Bignum Denominator { get; set; }
}

class BigMeanr {
    public static int Main(string[] argv) {
        var sum = new RationalBignum(0);
        var n = new Bignum(0);
        using (var s = new FileStream(argv[0])) {
            using (var r = new BinaryReader(s)) {
                try {
                    while (true) {
                        var flt = r.ReadSingle();
                        rat = new RationalBignum(flt);
                        sum += rat;
                        n++;
                    }
                }
                catch (EndOfStreamException) {
                    break;
                }
            }
        }
        Console.WriteLine("The mean is: {0}", sum / n);
    }
}

Just remember, there are more numeric types out there than the ones your compiler offers you.

Answer 11

This is a classic divide-and-conquer type problem.

The issue is that the average of a large set of numbers is the same as the average of the first-half of the set, averaged with the average of the second-half of the set.

In other words:

AVG(A[1..N]) == AVG( AVG(A[1..N/2]), AVG(A[N/2..N]) )

Here is a simple, C#, recursive solution. Its passed my tests, and should be completely correct.

public struct SubAverage
{
    public float Average;
    public int   Count;
};

static SubAverage AverageMegaList(List<float> aList)
{
    if (aList.Count <= 500) // Brute-force average 500 numbers or less.
    {
        SubAverage avg;
        avg.Average = 0;
        avg.Count   = aList.Count;
        foreach(float f in aList)
        {
            avg.Average += f;
        }
        avg.Average /= avg.Count;
        return avg;
    }

    // For more than 500 numbers, break the list into two sub-lists.
    SubAverage subAvg_A = AverageMegaList(aList.GetRange(0, aList.Count/2));
    SubAverage subAvg_B = AverageMegaList(aList.GetRange(aList.Count/2, aList.Count-aList.Count/2));

    SubAverage finalAnswer;
    finalAnswer.Average = subAvg_A.Average * subAvg_A.Count/aList.Count + 
                          subAvg_B.Average * subAvg_B.Count/aList.Count;
    finalAnswer.Count = aList.Count;

    Console.WriteLine("The average of {0} numbers is {1}",
        finalAnswer.Count, finalAnswer.Average);
    return finalAnswer;
}

Answer 12

Why not just scale the numbers (down) before computing the average?

Answer 13

Sorry for the late comment, but isn't it the formula above provided by Joel Coehoorn rewritten wrongly?

I mean, the basic formula is right:

Given:

A = current avg C = count of items V = next value in the sequence

The next average (A1) is:

A1 = ( (C * A) + V ) / ( C + 1 )

But instead of:

A1 = C/(C+1) * A/(C+1) + V/(C+1)

shouldn't we have:

A1 = C/(C+1) * A + V/(C+1)

That would explain kastermester's post:

"My math ticks off here - You have C, which you say "go towards infinity" or at least, a really big number, then: C/(C+1) goes towards 1. A /(C+1) goes towards 0. V/(C+1) goes towards 0. All in all: A1 = 1 * 0 + 0 So put shortly A1 goes towards 0 - seems a bit off. – kastermester"

Because we would have A1 = 1 * A + 0, i.e., A1 goes towards A, which it's right.

I've been using such method for calculating averages for a long time and the aforementioned precision problems have never been an issue for me.