﻿ Tolerant Comparison

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) whereis 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+⍵}  ⍝ ⌈
```
For example:
```   ⎕←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.
```

Previously appeared as the J Wiki Essay Tolerant Comparison, 2006-01-27.

 created: 2006-01-27 17:00 updated: 2014-10-28 01:35