3

I am trying to calculate average for an array of floats. I need to use indices because this is inside a binary search so the top and bottom will move. (Big picture we are trying to optimize a half range estimation so we don't have to re-create the array each pass).

Anyway I wrote a custom average loop and I'm getting 2 places less accuracy than the c# Average() method

float test = input.Average();

int count = (top - bottom) + 1;//number of elements in this iteration
int pos = bottom;
float average = 0f;//working average
while (pos <= top)
{
     average += input[pos];
     pos++;
}
average = average / count;

example:

0.0371166766 - c#
0.03711666 - my loop

125090.148 - c#
125090.281 - my loop

http://pastebin.com/qRE3VrCt

Eric Lippert
  • 647,829
  • 179
  • 1,238
  • 2,067
straver907
  • 33
  • 1
  • 4
  • 2
    try storing `average` as a double and converting to a `float` at the end. – Servy Feb 12 '13 at 18:32
  • 2
    I'd also rename your accumulator `sum` and use a new variable `average` in the end. – CodesInChaos Feb 12 '13 at 18:36
  • 1
    Floating point numbers are almost always only an approximation. If your average calculation differs from the c# Average() you will get different results. Have a look at this: http://stackoverflow.com/questions/4664662/understanding-floating-point-problems – Jobo Feb 12 '13 at 18:43
  • @Jobo Yes, they are an approximation, but adjusting your algorithm can reduce the error. – Servy Feb 12 '13 at 18:49

3 Answers3

5

I'm getting 2 places less accuracy than the c# Average()

No, you are only losing 1 significant digit. The float type can only store 7 significant digits, the rest are just random noise. Inevitably in a calculation like this, you can accumulate round-off error and thus lose precision. Getting the round-off errors to balance out requires luck.

The only way to avoid it is to use a floating point type that has more precision to accumulate the result. Not an issue, you have double available. Which is why the Linq Average method looks like this:

   public static float Average(this IEnumerable<float> source) {
       if (source == null) throw Error.ArgumentNull("source");
       double sum = 0;         // <=== NOTE: double
       long count = 0;
       checked {
           foreach (float v in source) {
               sum += v;
               count++;
           }
       }
       if (count > 0) return (float)(sum / count);
       throw Error.NoElements();
   }

Use double to reproduce the Linq result with a comparable number of significant digits in the result.

Hans Passant
  • 922,412
  • 146
  • 1,693
  • 2,536
2

I'd rewrite this as:

int count = (top - bottom) + 1;//number of elements in this iteration
double sum = 0;
for(int i = bottom; i <= top; i++)
{
     sum += input[i];
}
float average = (float)(sum/count);

That way you're using a high precision accumulator, which helps reduce rounding errors.

btw. if performance isn't that important, you can still use LINQ to calculate the average of an array slice:

input.Skip(bottom).Take(top - bottom + 1).Average()

I'm not entirely sure if that fits your problem, but if you need to calculate the average of many subarrays, it can be useful to create a persistent sum array, so calculating an average simply becomes two table lookups and a division.

CodesInChaos
  • 106,488
  • 23
  • 218
  • 262
2

Just to add to the conversation, be careful when using Floating point primitives.

What Every Computer Scientist Should Know About Floating-Point Arithmetic

Internally floating point numbers store additional least significant bits that are not reflected in the displayed value (aka: Guard Bits or Guard Digits). They are, however, utilized when performing mathematical operations and equality checks. One common result is that a variable containing 0f is not always zero. When accumulating floating point values this can also lead to precision errors.

Use Decimal for your accumulator:

  1. Will not have rounding errors due to Guard Digits
  2. Is a 128bit data type (less likely to exceed Max Value in your accumulator).

For more info: What is the difference between Decimal, Float and Double in C#?

Community
  • 1
  • 1
JFish222
  • 1,026
  • 7
  • 11