What is a good solution for calculating an average where the sum of all values exceeds a double's limits?

java algorithm statistics
Simon picture Simon · Dec 18, 2009 · Viewed 29.6k times · Source

I have a requirement to calculate the average of a very large set of doubles (10^9 values). The sum of the values exceeds the upper bound of a double, so does anyone know any neat little tricks for calculating an average that doesn't require also calculating the sum?

I am using Java 1.5.

Answer

martinus picture martinus · Dec 19, 2009

You can calculate the mean iteratively. This algorithm is simple, fast, you have to process each value just once, and the variables never get larger than the largest value in the set, so you won't get an overflow.

double mean(double[] ary) {
  double avg = 0;
  int t = 1;
  for (double x : ary) {
    avg += (x - avg) / t;
    ++t;
  }
  return avg;
}

Inside the loop avg always is the average value of all values processed so far. In other words, if all the values are finite you should not get an overflow.

Related questions

Finding the max/min value in an array of primitives using Java

It's trivial to write a function to determine the min/max value in an array, such as: /** * * @param chars * @return the max value in the array of chars */ private static int maxValue(char[] chars) { int max = chars[0]; for (int ktr = 0; …

Read More
Generating all permutations of a given string

What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?

Read More
What's the best way to build a string of delimited items in Java?

While working in a Java app, I recently needed to assemble a comma-delimited list of values to pass to another web service without knowing how many elements there would be in advance. The best I could come up with off …

Read More