# Essays/Tolerant Comparison

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 _4.44089e_16

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).

7 = 100 * 0.07 1 2 = *: %: 2 1

## Contents

## 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 region of tolerant equality for a complex number was elucidated by Jay Foad of Dyalog Limited 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-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.

## Tolerant Index-Of

If index-of is applied to floating-point numbers
and it is known that tolerant comparison
is not required,
then` i.!.0 `(exact index-of) instead of` i. `(tolerant index-of)
is more efficient.

## Tolerant Floor and Ceiling

Some special considerations are necessary for meaningful floor and ceiling
operations. For small numbers `a`, we would like `<.a` to be
equal to `n` if `n` is an integer which is tolerantly equal
to `a`. However, when `a` is large, there may be multiple
integers which are tolerantly equal to `a`:

a =. 2^45 a = a+2 1 a = a+i:4 0 0 1 1 1 1 1 0 0

It is certainly unreasonable to make `<.a` larger than `a`
by more than 1. Additionally, we would like for `<.a` to be less
than or equal to `>.a` for all `a` (and in fact, our final
solution will have equality if and only if `a` is tolerantly equal
to an integer). To satisfy these constraints, we ensure that `<.a`
exceeds `a` by at most 0.5, and that `a` exceeds
`>.a` by less than 0.5. Thus `(<.->.) a` is an integer which
is less than 1, and hence less than or equal to zero—we have
`(<.a) <: (>.a)` as desired.

The algorithm used by J (see `tfloor` and `tceiling` below)
starts with the integer nearest to `a`, rounding up if `0.5
(=!.0) 1|a`. Then, to obtain the floor of `a`, we subtract one
if the result is tolerantly greater than `a`. Since the rounded
number was within 0.5 of `a`, the smallest this number can be is
`a - 0.5`. Similarly, for the ceiling, we add one if it is tolerantly
less than `a`.

## 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 Roger Hui.