Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can a set of floating-point numbers be all above average?

I'm dealing with code which essentially boils down to this:

float child[24];
// assume child[] is filled here with some values
float sum = 0;
float avg;
for (int i = 0; i < 24; i++)
  sum += child[i];
avg = sum / 24;

int n_above_avg = 0;
int n_below_avg = 0;
for (int i = 0; i < 24; i++)
  if (child[i] <= avg)
    n_below_avg++;
  else
    n_above_avg++;

Because of floating-point imprecisions, is it possible at the end of this code for n_below_avg to be equal to 0? Assume no overflow can occur, and that all programmers are good-looking.

like image 895
lindelof Avatar asked Dec 16 '22 04:12

lindelof


1 Answers

With the computation of avg that you use, it is technically possible for all elements of an array of floats to be above avg.

Indeed, if all elements have the same value v and cause approximations such that the computed avg is rounded down with respect to the mathematical result v, then all elements in the array are larger than avg.

The sort of value v that would cause such a behavior is a value with bits set down to the least significant bits of its significand, so that adding the value to itself 23 times and dividing by 24 causes rounding. If I had to find one, I would enumerate floats one by one until I find one such value, confident it will only take a fraction of a second before one is found.

Techniques exist to compute the exact sum of an array of floats. One algorithm is famously implemented within Python. Using these techniques, it is possible to compute the correctly rounded average of the array. If avg was the correctly rounded average of the array, then I am confident that it would be impossible for all elements in the array to be above it.

like image 65
Pascal Cuoq Avatar answered Feb 01 '23 16:02

Pascal Cuoq