Essays/Tolerant Comparison

The = dictionary page defines equality with a tolerance t thus: for finite x and y , x=y  is 1 if the magnitude of x-y does not exceed t times the larger of the magnitudes of x and y .

The tolerance is normally 2^_44 . Appendix C, System Conventions and Limits, says that the tolerance is less than or equal to 2^_34 . Historically, the upper bound on the tolerance was chosen so that comparisons involving 32-bit integers are exact (as if the tolerance is 0).

Model of Tolerant Equal

Comparison involving a larger tolerance can be modelled readily by implementing the description in the = page. The phrase <:!.0 means exact <: (as if the tolerance is 0).

   teq=: 1 : '|@- <:!.0 m * >.&|'

   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, APL 2010, Berlin, 2010-09-16.

The definition of tolerant equality implies that the closed interval of numbers tolerantly equal to a real number x has endpoints x*1-t and x%1-t .

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=.t*|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)=t*|u . That is, the ratio between |u-z and |u is t , 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-t  collinear with z and the origin.

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"0/~ 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"0/~ 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

Comparisons with 0

A further consequence is that comparisons with 0 are exact. By definition, x=!.t y if (|x-y) <:!.0 t * x>.&|y .  If x is 0,  we get:

(|x-y) <:!.0 t * x>.&|y
(|0-y) <:!.0 t * 0>.&|y
(|y) <:!.0 t * |y

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

Comparisons with Infinity

Tolerant comparison is meaningless with infinite arguments. By definition, x=!.t y if (|x-y) <:!.0 t * x>.&|y .  If x and y are both infinite with the same sign (both _ or both __ ), the phrase x-y is a NaN error . Otherwise, if x or y is infinite or if both are infinite but with different signs,

(|x-y) <:!.0 t * x>.&|y
_ <:!.0 t * _
_ <:!.0 _
1

That is, infinity or negative infinity is "tolerantly equal" to every other number except itself.

Models

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

teq     =: 1 : '|@- <:!.0 m * >.&|'           NB. =   equal
tne     =: 1 : '[: -. m teq'                  NB. ~:  not equal
tlt     =: 1 : '< !.0 *. m tne'               NB. <   less than
tle     =: 1 : '<:!.0 +. m teq'               NB. <:  less than or equal
tge     =: 1 : '>:!.0 +. m teq'               NB. >:  greater than or equal
tgt     =: 1 : '> !.0 *. m tne'               NB. >   greater than

tfloor  =: 1 : '<.!.0@(0.5&+) ([ - m tgt) ]'  NB. <.  floor
tceiling=: 1 : '<.!.0@(0.5&+) ([ + m tlt) ]'  NB. >.  ceiling

For example:

   ] y=: 100+i:6
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

Contributed by RogerHui.