Get next smallest Double number

Question

As part of a unit test, I need to test some boundary conditions. One method accepts a System.Double argument.

Is there a way to get the next-smallest double value? (i.e. decrement the mantissa by 1 unit-value)?

I considered using Double.Epsilon but this is unreliable as it's only the smallest delta from zero, and so doesn't work for larger values (i.e. 9999999999 - Double.Epsilon == 9999999999).

So what is the algorithm or code needed such that:

NextSmallest(Double d) < d

...is always true.

Answer 1

The Wikipedia page on double-precision floating point is here: http://en.wikipedia.org/wiki/Double_precision_floating-point_format

For fun I wrote some code to break out the binary representation of the double format, decrements the mantissa and recomposes the resultant double. Because of the implicit bit in the mantissa we have to check for it and modify the exponent accordingly, and it might fail near the limits.

Here's the code:

public static double PrevDouble(double src)
{
    // check for special values:
    if (double.IsInfinity(src) || double.IsNaN(src))
        return src;
    if (src == 0)
        return -double.MinValue;

    // get bytes from double
    byte[] srcbytes = System.BitConverter.GetBytes(src);

    // extract components
    byte sign = (byte)(srcbytes[7] & 0x80);
    ulong exp = ((((ulong)srcbytes[7]) & 0x7F) << 4) + (((ulong)srcbytes[6] >> 4) & 0x0F);
    ulong mant = ((ulong)1 << 52) | (((ulong)srcbytes[6] & 0x0F) << 48) | (((ulong)srcbytes[5]) << 40) | (((ulong)srcbytes[4]) << 32) | (((ulong)srcbytes[3]) << 24) | (((ulong)srcbytes[2]) << 16) | (((ulong)srcbytes[1]) << 8) | ((ulong)srcbytes[0]);

    // decrement mantissa
    --mant;

    // check if implied bit has been removed and shift if so
    if ((mant & ((ulong)1 << 52)) == 0)
    {
        mant <<= 1;
        exp--;
    }

    // build byte representation of modified value
    byte[] bytes = new byte[8];
    bytes[7] = (byte)((ulong)sign | ((exp >> 4) & 0x7F));
    bytes[6] = (byte)((((ulong)exp & 0x0F) << 4) | ((mant >> 48) & 0x0F));
    bytes[5] = (byte)((mant >> 40) & 0xFF);
    bytes[4] = (byte)((mant >> 32) & 0xFF);
    bytes[3] = (byte)((mant >> 24) & 0xFF);
    bytes[2] = (byte)((mant >> 16) & 0xFF);
    bytes[1] = (byte)((mant >> 8) & 0xFF);
    bytes[0] = (byte)(mant & 0xFF);

    // convert back to double and return
    double res = System.BitConverter.ToDouble(bytes, 0);
    return res;
}

All of which gives you a value that is different from the initial value by a change in the lowest bit of the mantissa... in theory :)

Here's a test:

public static Main(string[] args)
{
    double test = 1.0/3;
    double prev = PrevDouble(test);
    Console.WriteLine("{0:r}, {1:r}, {2:r}", test, prev, test - prev);
}

Gives the following results on my PC:

0.33333333333333331, 0.33333333333333326, 5.5511151231257827E-17

The difference is there, but is probably below the rounding threshold. The expression test == prev evaluates to false though, and there is an actual difference as shown above :)

Answer 2

If your numbers are finite, you can use a couple of convenient methods in the BitConverter class:

long bits = BitConverter.DoubleToInt64Bits(value);
if (value > 0)
    return BitConverter.Int64BitsToDouble(bits - 1);
else if (value < 0)
    return BitConverter.Int64BitsToDouble(bits + 1);
else
    return -double.Epsilon;

IEEE-754 formats were designed so that the bits that make up the exponent and mantissa together form an integer that has the same ordering as the floating-point numbers. So, to get the largest smaller number, you can subtract one from this number if the value is positive, and you can add one if the value is negative.

The key reason why this works is that the leading bit of the mantissa is not stored. If your mantissa is all zeros, then your number is a power of two. If you subtract 1 from the exponent/mantissa combination, you get all ones and you'll have to borrow from the exponent bits. In other words: you have to decrement the exponent, which is exactly what we want.