Enumerating 32 bits Floats

This week, let’s go back to (low level) programming, with IEEE floats. To unit test a function of float, it does not sound unreasonable to just enumerate them all. But how do we do that efficiently? Clearly f++ will not get us there.

Buoys_1

Nor will the machine-epsilon (the std::numeric_limits::epsilon()) because this value works fine around 1, but as the value diverges from 1, the epsilon basically becomes useless. We would either need a magnitude-dependent epsilon (which the standard library does not provide) or a way of enumerating explicitly the floats in increasing or decreasing order (something also not provided by the standard library). Well, let’s see how we can do that

First, let us have a look at how floats are structured. We discussed that previously, but let’s review it here anyway. In a IEEE-754 32bits (single precision) float, you have a sign bit, 8 exponent bits, and 23 mantissa (or “precision”) bits. The layout is as follows:

(From Wikipedia)

(From Wikipedia)

The value of a float with bits s, exponent e, and mantissa bits m, is given by:

\displaystyle v=(-1)^s 2^{e-127} \left(1+\sum_{i=1}^{23} 2^{-i}m_i\right)

The troublesome bit here is the sign bit. IEEE floats use one’s complement, meaning that we can’t use the usual two’s complement we’re used to use with integers. So enumerating floats from the smallest to the largest won’t be as easy as going from -2^{31} to 2^{31}-1 by steps of 1. First, let’s have a look at the general “address space” of floats:

float-layout

In the lower half, floats increase up, but in the top half, they decrease up, a weird effect entirely due to the sign bits. A “walk” from 0, going up, wrapping around passed MAX_FLOAT then to the "minus MAX_FLOAT", is shown in the following figure:

float-layout-increment

And enumerating floats going down, the path would be:

float-layout-decrement

Let's implement the thing as a class in order to encapsulate all the details. The class implementation would look something like:

class float_enum
 {
  private:

  enum { float_enum_min=0xffffffffu,
         float_enum_max=0x7fffffffu,
         float_enum_minus_zero=0x80000000u };

  unsigned i;


  void next()
   {
    if (i==float_enum_minus_zero+1)
     i=0;
    else
     if (i==float_enum_max)
      i=float_enum_min;
     else 
      if (i>float_enum_minus_zero)
       i--;
      else
       i++;
   }

  void prev()
   {
    if (i==float_enum_min)
     i=float_enum_max;
    else
     if (i==0)
      i=float_enum_minus_zero+1;
     else
      if (i<float_enum_minus_zero)
       i--;
      else
       i++;
   }


  float as_float() const { return *reinterpret_cast<const float*>(&i); }

 public:

  operator float() const { return as_float(); }
  float operator++()    { next(); return as_float(); } // postfix
  float operator++(int) { float f=as_float(); next(); return f; } // prefix
  float operator--()    { prev(); return as_float(); } // postfix
  float operator--(int) { float f=as_float(); prev(); return f; } // prefix


  float_enum(float initial=-std::numeric_limits<float>::max()) 
   :i(*reinterpret_cast<unsigned *>(&initial)) {}
 };

Here, all the magic occurs in the next() and prev() member functions. Each reproduce the walk shown in the diagrams, with the added flourish skipping of skipping -0.


float_enum f;
for (unsigned l=0,i=0;l<=i;l=i,i++,f++)
 if (!isnan(f))
  {
   ...use f...
  }

Remark the isnan(f) in the code above. In general, you should expect the Spanish inquisition NaNs, because in many context they can be very useful, especially to encode non-initialized floats—zero sucks at this.

In conclusion, enumerating floats in increasing or decreasing order is complicated by the fact that it uses one's complement, and that the standard library only provides a mostly useless epsilon. But, on the bright side, we now have a way of enumerating all values, including the NaNs.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: