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. 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:

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: 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: And enumerating floats going down, the path would be: 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.