Tolerant Comparison

Roger Hui

Tolerant comparison ameliorates the ugly realities of finite-precision representation and arithmetic. For example, 7 is not exactly equal to 100×0.07 , nor 2 exactly equal to the square of the square root of 2 :

   7 - 100×0.07
¯8.88178e¯16
   2 - (2*0.5)*2
¯4.44089e¯16

The Dyalog APL Language Reference defines equality with a tolerance ⎕ct thus: Two numbers x and y are equal if (|x-y)≤⎕ct×(|x)⌈(|y) where ≤ is applied without tolerance.

   7 = 100 × 0.07
1
   2 = (2*0.5)*2
1

The tolerance ⎕ct may be assigned any value in the range from 0 to 2*¯32 . Historically, the upper bound 2*¯32 was chosen so that comparisons involving 32-bit signed integers can be implemented as if the tolerance were 0.

Model of Tolerant Equal

Tolerant comparison can be modelled by implementing the description above as a dynamic operator. The model is useful for exploring different tolerances, even those that are illegal settings for ⎕ct .

   teq←{⎕ct←0 ⋄ (|⍺-⍵)≤⍺⍺×(|⍺)⌈(|⍵)}

   1 (0.1 teq) 0.899
0
   1 (0.1 teq) 0.9
1
   1 (0.1 teq) 1.1
1
   1 (0.1 teq) 1.2
0
   1 (0.1 teq) 0.899 0.9 1.1 1.12
0 1 1 0

Region of Tolerant Equality

Adapted from R.K.W. Hui, Hashing for Tolerant Index Of, APL2010, Berlin, 2010-09-16. The region of tolerant equality for a complex number was elucidated by Jay Foad in 2010.

The definition of tolerant equality implies that the closed interval of numbers tolerantly equal to a real number x has endpoints x×1-⎕ct and x÷1-⎕ct .

As the diagram (exaggeratingly) illustrates, the interval is not symmetric around x . The diagram is reflected about the origin if x is negative.

The region of numbers tolerantly equal to a complex number z is a near-circle with radius r←⎕ct×|z .

More precisely, it is the union of two circular regions: The smaller (in black) is centered on z with radius r . The larger derives as follows. A point u on the boundary with magnitude ≥ |z satisfies (|u-z)=⎕ct×|u . That is, the ratio between |u-z and |u is ⎕ct , a constant; therefore, that boundary is a circle of Apollonius with foci z and the origin. The larger circle (in red) circumscribes the two points p and q on the smaller circle with magnitude |z (in green) and the point s with magnitude (|z)÷1-⎕ct collinear with z and the origin.

r←⎕ct×|z (|u-z) = ⎕ct×|u (|p) = |z (|q) = |z (|s) = (|z)÷1-⎕ct

Tolerance Less Than 1

A consequence of the definition is that tolerances greater than or equal to 1 do not give meaningful results:

   1 (0.99 teq) 100
1
   1 (0.99 teq) 100.1
0
   1 (0.999 teq) 1000
1
   1 (0.999 teq) 1000.1
0

   1 (1 teq) 1e9
1

   ∘.(1 teq)⍨ ?10⍴2e9
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
   ∘.(1 teq)⍨ ?10⍴0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1

(That is, at tolerance ≥ 1 a number is equal to any other number.)

Comparisons with 0

A further consequence is that comparisons with 0 are exact. By definition, x=y with tolerance t if (|x-y) ≤ t × (|x)⌈(|y) . If x is 0 , we get:

(|x-y) ≤ t × (|x)⌈(|y)
(|0-y) ≤ t × 0⌈|y
(|y) ≤ t × |y

Since t is less than 1, |y and hence y itself must be exactly 0 for the propositions to hold.

This property can be exploited to effect exact comparison between x and y even when ⎕ct is non-zero: write 0=x-y instead of x=y .

Tolerant Index-Of

If index-of is applied to floating-point numbers and it is known that tolerant comparison is not required, then {⎕ct←0 ⋄ ⍺⍳⍵} instead of ⍳ , exact index-of instead of tolerant index-of, is faster.

Models

The following models of tolerant comparisons are as presented in Robert Bernecky, Comparison Tolerance, SHARP APL Technical Notes 23, 1977-06-10; Revision 1, 1978-07-15.

teq      ← {⎕ct←0 ⋄ (|⍺-⍵)≤⍺⍺×(|⍺)⌈(|⍵)}  ⍝ =
tne      ← {~⍺ (⍺⍺ teq) ⍵}                ⍝ ≠
tlt      ← {⎕ct←0 ⋄ (⍺<⍵)∧⍺(⍺⍺ tne)⍵}     ⍝ <
tle      ← {⎕ct←0 ⋄ (⍺≤⍵)∨⍺(⍺⍺ teq)⍵}     ⍝ ≤
tge      ← {⎕ct←0 ⋄ (⍺≥⍵)∨⍺(⍺⍺ teq)⍵}     ⍝ ≥
tgt      ← {⎕ct←0 ⋄ (⍺>⍵)∧⍺(⍺⍺ tne)⍵}     ⍝ >

tfloor   ← {⎕ct←0 ⋄ c-⍵(⍺⍺ tlt)c←⌊0.5+⍵}  ⍝ ⌊
tceiling ← {⎕ct←0 ⋄ c+⍵(⍺⍺ tgt)c←⌊0.5+⍵}  ⍝ ⌈

   ⎕←y←94+⍳13
94 95 96 97 98 99 100 101 102 103 104 105 106

   100 (0.05 teq) y
0 1 1 1 1 1 1 1 1 1 1 1 0
   100 (0.05 tne) y
1 0 0 0 0 0 0 0 0 0 0 0 1
   100 (0.05 tlt) y
0 0 0 0 0 0 0 0 0 0 0 0 1
   100 (0.05 tle) y
0 1 1 1 1 1 1 1 1 1 1 1 1
   100 (0.05 tge) y
1 1 1 1 1 1 1 1 1 1 1 1 0
   100 (0.05 tgt) y
1 0 0 0 0 0 0 0 0 0 0 0 0

   (0.05 tfloor  ) y÷100
0 0 1 1 1 1 1 1 1 1 1 1 1
   (0.05 tceiling) y÷100
1 1 1 1 1 1 1 1 1 1 1 1 2

Alternatively, the computations can be modelled as a single dyadic dynamic operator, with the left operand being a function and a right operand the tolerance.

tol←{                           
    ⎕ct←0                       
    f←⊃⎕cr'f'⊣0(f←⍺⍺)0           
                                
    f='⌊' :c-⍵(< tol ⍵⍵)c←⌊0.5+⍵
    f='⌈' :c+⍵(> tol ⍵⍵)c←⌊0.5+⍵                        
    e←(|⍺-⍵)≤⍵⍵×(|⍺)⌈(|⍵)       
    f='=' : e                     
    f='≠' :~e                    
    f∊'≤≥':e∨⍺ ⍺⍺ ⍵           
    f∊'<>':e<⍺ ⍺⍺ ⍵                 
} 

   100 (= tol 0.05) y
0 1 1 1 1 1 1 1 1 1 1 1 0
   100 (≠ tol 0.05) y
1 0 0 0 0 0 0 0 0 0 0 0 1
   ⍝ etc.