Increment a Python floating point value by the smallest possible amount

Question

How can I increment a floating point value in python by the smallest possible amount?

---

Background: I'm using floating point values as dictionary keys.

Occasionally, very occasionally (and perhaps never, but not certainly never), there will be collisions. I would like to resolve these by incrementing the floating point value by as small an amount as possible. How can I do this?

In C, I would twiddle the bits of the mantissa to achieve this, but I assume that isn't possible in Python.

Answer 1

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.

Answer 2

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().

A simpler alternative to math.copysign(math.inf, x) is to simply substitute 2*x.

Answer 3

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

Answer 4

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

Answer 5

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.

Answer 6

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.

Answer 7

A better answer (now I'm just doing this for fun...), motivated by twiddling the bits. Handling the carry and overflows between parts of the number of negative values is somewhat tricky.

import struct

def floatToieee754Bits(f):
    return struct.unpack('<Q', struct.pack('<d', f))[0]

def ieee754BitsToFloat(i):
    return struct.unpack('<d', struct.pack('<Q', i))[0]

def incrementFloat(f):
    i = floatToieee754Bits(f)
    if f >= 0:
        return ieee754BitsToFloat(i+1)
    else:
        raise Exception('f not >= 0: unsolved problem!')

Answer 8

Instead of resolving the collisions by changing the key, how about collecting the collisions? IE:

bag = {}
bag[1234.] = 'something'

becomes

bag = collections.defaultdict(list)
bag[1234.].append('something')

would that work?

Answer 9

For colliding key k, add: k / 2⁵⁰

---

Interesting problem. The amount you need to add obviously depends on the magnitude of the colliding value, so that a normalized add will affect only the least significant bits.

It's not necessary to determine the smallest value that can be added. All you need to do is approximate it. The FPU format provides 52 mantissa bits plus a hidden bit for 53 bits of precision. No physical constant is known to anywhere near this level of precision. No sensor is able measure anything near it. So you don't have a hard problem.

In most cases, for key k, you would be able to add k/2⁵³, because of that 52-bit fraction plus the hidden bit.

But it's not necessary to risk triggering library bugs or exploring rounding issues by shooting for the very last bit or anything near it.

So I would say, for colliding key k, just add k / 2⁵⁰ and call it a day.¹

---

^{1. Possibly more than once until it doesn't collide any more, at least to foil any diabolical unit test authors.}

Answer 10

import sys
>>> sys.float_info.epsilon
2.220446049250313e-16

Answer 11

Instead of modifying your float timestamp, use a tuple for every key as Mark Ransom suggests where the tuple (x,y) is composed of x=your_unmodified_time_stamp and y=(extremely unlikely to be a same value twice).

So:

1. x just is the unmodified timestamp and can be the same value many times;
2. y you can use:
   1. a random integer number from a large range,
   2. serial integer (0,1,2,etc),
   3. UUID.

While 2.1 (random int from a large range) there works great for ethernet, I would use 2.2 (serializer) or 2.3 (UUID). Easy, fast, bulletproof. For 2.2 and 2.3 you don't even need collision detection (you might want to still have it for 2.1 as ethernet does.)

The advantage of 2.2 is that you can also tell, and sort, data elements that have the same float time stamp.

Then just extract x from the tuple for any sorting type operations and the tuple itself is a collision free key for the hash / dictionary.

Edit

I guess example code will help:

#!/usr/bin/env python

import time
import sys
import random

#generator for ints from 0 to maxinteger on system:
serializer=(sn for sn in xrange(0,sys.maxint))

#a list with guranteed collisions:
times=[]
for c in range(0,35):
   t=time.clock()
   for i in range(0,random.choice(range(0,4))):
      times.append(t)

print len(set(times)), "unique items in a list of",len(times)      

#dictionary of tuples; no possibilities of collisions:
di={}   
for time in times:
    sn=serializer.next()
    di[(time,sn)]='Element {}'.format(sn)

#for tuples of multiple numbers, Python sorts
# as you expect: first by t[0] then t[1], until t[n]
for key in sorted(di.keys()):
    print "{:>15}:{}".format(key, di[key]) 

Output:

26 unique items in a list of 55
  (0.042289, 0):Element 0
  (0.042289, 1):Element 1
  (0.042289, 2):Element 2
  (0.042305, 3):Element 3
  (0.042305, 4):Element 4
  (0.042317, 5):Element 5
  # and so on until Element n...

Answer 12

Here it part of it. This is dirty and slow, but maybe that is how you like it. It is missing several corner cases, but maybe this gets someone else close.

The idea is to get the hex string of a floating point number. That gives you a string with the mantissa and exponent bits to twiddle. The twiddling is a pain since you have to do all it manually and keep converting to/from strings. Anyway, you add(subtract) 1 to(from) the last digit for positive(negative) numbers. Make sure you carry through to the exponent if you overflow. Negative numbers are a little more tricky to make you don't waste any bits.

def increment(f):
    h = f.hex()
    # decide if we need to increment up or down
    if f > 0:
        sign = '+'
        inc = 1
    else:
        sign = '-'
        inc = -1
    # pull the string apart
    h = h.split('0x')[-1]
    h,e = h.split('p')
    h = ''.join(h.split('.'))
    h2 = shift(h, inc)
    # increase the exponent if we added a digit
    h2 = '%s0x%s.%sp%s' % (sign, h2[0], h2[1:], e)
    return float.fromhex(h2)

def shift(s, num):
    if not s:
        return ''
    right = s[-1]
    right = int(right, 16) + num
    if right > 15:
        num = right // 16
        right = right%16
    elif right < 0:
        right = 0
        num = -1
    else:
        num = 0
    # drop the leading 0x
    right = hex(right)[2:]
    return shift(s[:-1], num) + right

a = 1.4e4
print increment(a) - a
a = -1.4e4
print increment(a) - a

a = 1.4
print increment(a) - a

Answer 13

I think you mean "by as small an amount possible to avoid a hash collision", since for example the next-highest-float may already be a key! =)

while toInsert.key in myDict: # assumed to be positive
    toInsert.key *= 1.000000000001
myDict[toInsert.key] = toInsert

That said you probably don't want to be using timestamps as keys.

Answer 14

After Looking at Autopopulated's answer I came up with a slightly different answer:

import math, sys

def incrementFloatValue(value):
    if value == 0:
        return sys.float_info.min                                
    mant, exponent = math.frexp(value)                                                   
    epsilonAtValue = math.ldexp(1, exponent - sys.float_info.mant_dig)                
    return math.fsum([value, epsilonAtValue])

Disclaimer: I'm really not as great at maths as I think I am ;) Please verify this is correct before using it. Also I'm not sure about performance

some notes:

• epsilonAtValue calculates how many bits are used for the mantissa (the maximum minus what is used for the exponent).
• I'm not sure if the math.fsum() is needed but hey it doesn't seem to hurt.

Answer 15

It turns out that this is actually quite complicated (maybe why seven people have answered without actually providing an answer yet...).

I think this is the right solution, it certainly seems to handle 0 and positive values correctly:

import math
import sys

def incrementFloat(f):
    if f == 0.0:
        return sys.float_info.min
    m, e = math.frexp(f)
    return math.ldexp(m + sys.float_info.epsilon / 2, e)