Fast comparison with a tolerance I am trying to find a way to compare two real numbers (actually floating-point) with a tolerance, i.e. test $|r-s|\le\epsilon$. Without loss of generality, $\epsilon=1$.

I want to do this by replacing the numbers by a discrete key computed on them in such a way that when two keys differ, they map two significantly distant numbers.

$$K(r)\ne K(s)\implies |r-s|\ge 1.$$

The converse,

$$K(r)=K(s)\implies |r-s|&lt;1.$$

may only partially hold, but should be false in a minority of the cases. ($K(r):=0$ is indeed a trivial solution to the first requirement, but is of no use because of the second.)

In my context (database search), the key being discrete and a single comparison for equality being sufficient are essential properties. 

The first idea that come to mind is simple rounding, or equivalently, flooring, i.e.

$$K(r):=\lfloor r\rfloor.$$

Anyway this doesn't work as all values in range $[r,r+1)$ map to $K(r)$; the values $1$ unit away from these span $(r-1,r+2)$, which maps to one of $r-1,r,r+1$. So you would need a triple equality test 

$$|r-s|&lt;1\implies \lfloor r\rfloor=\lfloor s\rfloor-1\lor \lfloor r\rfloor=\lfloor s\rfloor\lor \lfloor r\rfloor=\lfloor s\rfloor+1.$$

If I am right, the reasoning can be extended to any function $K$: the numbers that map to $K(r)$ are in the set $K^{-1}(K(r))$; the numbers one unit away are in the Minkowski sum $K^{-1}(K(r)) + (0,1)$, which cannot be covered by a single $K^{-1}(K(s))$.

I can also accept a scheme where the key function is computed differently for $s$, but the single comparison principle must remain

$$K(r)\ne L(s)\implies |r-s|\ge 1.$$

Is this a known problem ? Is there a solution or a workaround ?

Update: the problem statement was reformulated in the original text.
If for all $|r - s| &lt; 1$ it is the case that $K(r) = K(s)$ then $K$ is constant (exercise).

What you are asking is impossible.

One thing which is possible is to compare keys with three rather than two possible outcomes:


If $K(r)$ is close to $K(s)$ then $|r - s| &lt; 1$.
If $K(r)$ is far from $K(s)$ then $|r - s| \geq 1$.
Otherwise, we don't know.


Of course, the aim is that the third case happens as rarely as possible. One simple way to achieve this is to choose a random $x$ and some small (non-random) $\epsilon &gt; 0$, and to use
$$
K(r) = \lfloor r/\epsilon + x \rfloor.
$$
Under this definition, the only uncertainty is for $r,s$ at distance $(1-\epsilon,1+\epsilon)$. The random component mitigates even this uncertainty, albeit only by a little.