Intersection for lists of numeric data

I know that Intersection is a pattern matching function and will not evaluate list elements to determine if two or more list have equal elements. So my question is, what can be done to do this? Say, determine if two lists have numerically equal elements within some tolerance dx?

Answer

Closely related questions:

---

The most direct method is to make use of the SameTest option:

a = {1, 2.2, 3.14159};
b = {11/5, Pi, 1/2, 1/4};


Intersection[a, b, SameTest -> (Abs[# - #2] < 0.0001 &)]

{2.2, 3.14159}

This however requires a pairwise comparison that has a much higher computational complexity than the default method. A different method that does not require a pairwise compare will be much faster on long lists. Iff each list is internally free of duplicates and your tolerance requirement can be relaxed to rounding you could use this:

Cases[GatherBy[Join[b, a], Round[#, 0.0001] &], {x_, _} :> x]

{11/5, π}

Note here that the exact values are returned despite the use of Round, because list b is given first in Join.

The speed advantage can be great:

a = RandomReal[99, 1000];
b = RandomReal[99, 1000];

Intersection[a, b, SameTest -> (Abs[# - #2] < 0.0001 &)]       // Timing // First
Cases[GatherBy[Join[b, a], Round[#, 0.0001] &], {x_, __} :> x] // Timing // First

1.638

0.0011728

If a list is not internally free of duplicates any of those values will be returned as well:

a = {1, 2.2, 3.14159};
b = {11/5, Pi, 1/2, 0.5}; (* note 1/2 and 0.5 *)

Cases[GatherBy[Join[b, a], Round[#, 0.0001] &], {x_, __} :> x]

{11/5, π, 1/2}