Sorting floats

A floating-point mystery

Here's a bug I ran into several years ago. Assume we have a bunch of points defined by their coordinates and we want their pairwise distances in increasing order:

distances = [dist(x, y) for x, y in itertools.combinations(points, 2)]
distances.sort()

Here dist is a function that computes some kind of distance measure. The details don't matter much but let's say that it's Manhattan distance,

def dist(x, y):
    return sum(abs(a - b) for a, b in zip(x, y))

Now we have the distances in order so that distances[0] is the smallest and distances[-1] is the largest... right? But it turned out that distances[0] was not the same as min(distances).

If you want to ponder the mystery yourself, the question is how to complete the assignment points = ... so that the assertion at the end fails:

import itertools

def dist(x, y):
    return sum(abs(a - b) for a, b in zip(x, y))

points = ...

distances = [dist(x, y) for x, y in itertools.combinations(points, 2)]
distances.sort()

assert distances[0] == min(distances)

Read more…