Increment a Python floating point value by the smallest possible amount

Question

Since Python 3.9 there is math.nextafter in the stdlib. Read on for alternatives in older Python versions.

Increment a python floating point value by the smallest possible amount

The nextafter(x,y) functions return the next discretely different representable floating-point value following x in the direction of y. The nextafter() functions are guaranteed to work on the platform or to return a sensible value to indicate that the next value is not possible.

The nextafter() functions are part of POSIX and ISO C99 standards and is _nextafter() in Visual C. C99 compliant standard math libraries, Visual C, C++, Boost and Java all implement the IEEE recommended nextafter() functions or methods. (I do not honestly know if .NET has nextafter(). Microsoft does not care much about C99 or POSIX.)

None of the bit twiddling functions here fully or correctly deal with the edge cases, such as values going though 0.0, negative 0.0, subnormals, infinities, negative values, over or underflows, etc. Here is a reference implementation of nextafter() in C to give an idea of how to do the correct bit twiddling if that is your direction.

There are two solid work arounds to get nextafter() or other excluded POSIX math functions in Python < 3.9:

Use Numpy:

>>> import numpy
>>> numpy.nextafter(0,1)
4.9406564584124654e-324
>>> numpy.nextafter(.1, 1)
0.10000000000000002
>>> numpy.nextafter(1e6, -1)
999999.99999999988
>>> numpy.nextafter(-.1, 1)
-0.099999999999999992

Link directly to the system math DLL:

import ctypes
import sys
from sys import platform as _platform

if _platform == "linux" or _platform == "linux2":
    _libm = ctypes.cdll.LoadLibrary('libm.so.6')
    _funcname = 'nextafter'
elif _platform == "darwin":
    _libm = ctypes.cdll.LoadLibrary('libSystem.dylib')
    _funcname = 'nextafter'
elif _platform == "win32":
    _libm = ctypes.cdll.LoadLibrary('msvcrt.dll')
    _funcname = '_nextafter'
else:
    # these are the ones I have access to...
    # fill in library and function name for your system math dll
    print("Platform", repr(_platform), "is not supported")
    sys.exit(0)

_nextafter = getattr(_libm, _funcname)
_nextafter.restype = ctypes.c_double
_nextafter.argtypes = [ctypes.c_double, ctypes.c_double]

def nextafter(x, y):
    "Returns the next floating-point number after x in the direction of y."
    return _nextafter(x, y)

assert nextafter(0, 1) - nextafter(0, 1) == 0
assert 0.0 + nextafter(0, 1) > 0.0

And if you really really want a pure Python solution:

# handles edge cases correctly on MY computer 
# not extensively QA'd...
import math
# 'double' means IEEE 754 double precision -- c 'double'
epsilon  = math.ldexp(1.0, -53) # smallest double that 0.5+epsilon != 0.5
maxDouble = float(2**1024 - 2**971)  # From the IEEE 754 standard
minDouble  = math.ldexp(1.0, -1022) # min positive normalized double
smallEpsilon  = math.ldexp(1.0, -1074) # smallest increment for doubles < minFloat
infinity = math.ldexp(1.0, 1023) * 2

def nextafter(x,y):    
    """returns the next IEEE double after x in the direction of y if possible"""
    if y==x:
       return y         #if x==y, no increment

    # handle NaN
    if x!=x or y!=y:
        return x + y       

    if x >= infinity:
        return infinity

    if x <= -infinity:
        return -infinity

    if -minDouble < x < minDouble:
        if y > x:
            return x + smallEpsilon
        else:
            return x - smallEpsilon  

    m, e = math.frexp(x)        
    if y > x:
        m += epsilon
    else:
        m -= epsilon

    return math.ldexp(m,e)

Or, use Mark Dickinson's excellent solution

Obviously the Numpy solution is the easiest.

Python 3.9 and above

Starting with Python 3.9, released 2020-10-05, you can use the math.nextafter function:

math.nextafter(x, y)

Return the next floating-point value after x towards y.

If x is equal to y, return y.

Examples:

• math.nextafter(x, math.inf) goes up: towards positive infinity.

• math.nextafter(x, -math.inf) goes down: towards minus infinity.

• math.nextafter(x, 0.0) goes towards zero.

• math.nextafter(x, math.copysign(math.inf, x)) goes away from zero.

See also math.ulp().

First, this "respond to a collision" is a pretty bad idea.

If they collide, the values in the dictionary should have been lists of items with a common key, not individual items.

Your "hash probing" algorithm will have to loop through more than one "tiny increments" to resolve collisions.

And sequential hash probes are known to be inefficient.

Read this: http://en.wikipedia.org/wiki/Quadratic_probing

Second, use math.frexp and sys.float_info.epsilon to fiddle with mantissa and exponent separately.

>>> m, e = math.frexp(4.0)
>>> (m+sys.float_info.epsilon)*2**e
4.0000000000000018

Forgetting about why we would want to increment a floating point value for a moment, I would have to say I think Autopulated's own answer is probably correct.

But for the problem domain, I share the misgivings of most of the responders to the idea of using floats as dictionary keys. If the objection to using Decimal (as proposed in the main comments) is that it is a "heavyweight" solution, I suggest a do-it-yourself compromise: Figure out what the practical resolution is on the timestamps, pick a number of digits to adequately cover it, then multiply all the timestamps by the necessary amount so that you can use integers as the keys. If you can afford an extra digit or two beyond the timer precision, then you can be even more confident that there will be no or fewer collisions, and that if there are collisions, you can just add 1 (instead of some rigamarole to find the next floating point value).

I recommend against assuming that floats (or timestamps) will be unique if at all possible. Use a counting iterator, database sequence or other service to issue unique identifiers.

Instead of incrementing the value, just use a tuple for the colliding key. If you need to keep them in order, every key should be a tuple, not just the duplicates.