SATN-23: Comparison Tolerance

SATN-23
Comparison Tolerance
Robert Bernecky




Abstract

The definition of tolerant comparison used in SHARP APL has been changed. This SATN describes the justification for and effects of that change.

Keywords: Tolerance
  Comparison
  ⎕ct
  Fuzz
  Floating point
  Error
  Fraction
 

Introduction

Error is inevitable in the computation and representation of numbers in any computer system. This is particularly true for large numbers and numbers containing a non-zero fraction.

APL facilitates the comparison of such numbers by providing the concept of a comparison tolerance, whereby two numbers are considered equal if they fall within this tolerance. The tolerance is controlled by the value of a system variable ⎕ct .

⎕ct defines a relational tolerance dependent on the magnitude of the larger of the numbers being compared. The definition used in the past, however, was tailored too much to the idiosyncracies of the computer, and too little to the needs of the APL user. It was difficult to model in APL, and yielded anomalous results.

R.H. Lathwell provided a more straightforward definition of tolerant comparison (Appendix 1) that does not differ greatly, in practical terms, from the old one, but is easier to comprehend.

This definition has been implemented in SHARP APL, with the exception of Lathwell’s definitions of floor and ceiling. The definitions of floor and ceiling used in SHARP APL were developed by D.L. Forkes and R. Bernecky (I.P. Sharp Associates, Toronto) and represent a slight variant of an algorithm proposed by L.M. Breed (IBM) - reference: IBM Technical Report TR03.023.

SHARP APL utilizes tolerant comparison in the following primitive functions, because they all imply some form of comparison between two numbers.

 less than  a<b
 less than or equal  a≤b
 equal  a=b
 greater than or equal a≥b
 greater than  a>b
 not equal  a≠b
 floor  ⌊a
 ceiling  ⌈a
 membership  a∊b
 index of  a⍳b

It is emphasized that no other primitive functions in SHARP APL use tolerant comparison.

Tolerant comparison considers two numbers to be equal if they are within some neighborhood. The neighborhood has a radius of ⎕ct times the larger of the two in absolute value. In the following, all primitive functions are exact (i.e. tolerant comparison is not used).

The formal definition for tolerant equality is now:

   ∇ r←a teq b
[1]  r←(|a-b)≤⎕ct×(|a)⌈|b
   ∇

Similarly,

tne a≠b    ~a teq b
tlt a<b (a<b)^a tne b
tle a≤b (a≤b)∨a teq b
tge a≥b (a≥b)∨a teq b
tgt a>b (a>b)^a tne b
teps a∊b ∨/a∘.teq ,b
tiota a⍳b ⎕io++/^\b∘.tne a
floor ⌊a (⌊.5+a)-(⌊.5+a) tgt a
ceiling    ⌈a (⌊.5+a)+(⌊.5+a) tlt a

Floor and Ceiling

Choice of a suitable definition for floor and ceiling is more subtle than one might expect. Anomalies tend to creep in when ⎕ct and the argument are large enough so that both integers adjacent to the argument are tolerantly equal to the argument.

Lathwell’s definition of floor as printed in the APL76 proceedings results in absolute fuzzing for arguments >1 :

   ∇ r←f0 a
[1]  r←⌊a+⎕ct×1⌊|a    ⍝ wrong
   ∇

Various decorations or changes to Lathwell’s definition don’t help:

   ∇ r←f1 a
[1]  r←⌊a+⎕ct×1⌈|a    ⍝ can produce results many integers
                        away from a
   ∇

   ∇ r←f2 a
[1]  r←⌊a+1⌊⎕ct×1⌈|a  ⍝ fails for large integral values 
                        of a
   ∇

We could alter the definition to:

   ∇ r←f3 a
[1]  r←⌊a+almost1⌊⎕ct×1⌈|a
   ∇

but the result is non-intuitive, and the value of almost1 is machine-dependent.

Forkes and Bernecky produced the following definition:

   ∇ r←f4 a
[1]  r←⌊a
[2]  r←r+(a teq r+1)^a tne r
   ∇

The result is the smaller integer, unless the argument is tolerantly equal only to the larger integer.

Breed pointed out an anomaly in this definition, for large arguments, and increasing values of ⎕ct :

      a←12346789123.8

      ⎕ct←1e¯15 ⋄ f4 a
123456789123
      ⎕ct←1e¯12 ⋄ f4 a
123456789124
      ⎕ct←1e¯10 ⋄ f4 a
123456789123

This oscillation of the result is undesirable.

Breed proposed the following algorithm:

   ∇ r←f5 a
[1]  r←(×a)×⌊almostpoint5+a   ⍝ nearest integer to a.
[2]  r←r-(r-a)>⎕ct×1⌈|a       ⍝ tgt, except near zero.
   ∇

This algorithm doesn’t oscillate, but still contains an arcane, machine-dependent constant.

Forkes then suggested a machine-independent variant that yields results only slightly different from f5 :

   ∇ r←floor a
[1]  r←(×a)×⌊.5+|a            ⍝ nearest integer to a.
[2]  r←r-(r-a)>⎕ct×1⌈|a
   ∇

floor differs functionally from f5 only in the treatment of large values of a such that

      (.5=1|a)^.5≤⎕ct×|a .

In such cases, f5 chooses the integer closer to zero, whereas floor chooses the integer farther away from zero. Since the choice is arbitrary, and since it is common practice to round n.5 up to n+1 , this seems reasonable.

floor is the algorithm now implemented in SHARP APL. The algorithm for ceiling is:

   ∇ r←ceiling a
[1]  r←-floor-a
   ∇

Breed has recently published “Definitions for Fuzzy Floor and Ceiling”, an IBM technical report TR03.034 - dated March 1977. The report is an analysis of several algorithms for floor and ceiling, including the floor presented here.
 

Significance of the New Definition

1)  Setting ⎕ct to a given value now implies that, to be considered equal, two numbers must be identical to approximately 10⍟÷⎕ct decimal digits.
Note: SHARP APL restricts the maximum value of ⎕ct to be <16*¯8 .
 
2)  It follows directly from the definition in the introduction that comparison of numbers of unlike signs, or comparison with zero, is exact.
 
3)  The current implementation of SHARP APL should product results identical to the models presented here.
 
4)  The definition is independent of the machine on which it is implemented. It is intended to facilitate interchange of applications.
 
5) 

Certain anomalies in the old definition disappear. Previously, comparisons of numbers very close to powers of 16 tended to produce strange results:

Consider the regions of tolerant equality for both definitions, using an absurdly large value of ⎕ct (.1).

Consider the point x=ugly , and the monotonically increasing points y=eq1, ne1, eq2, ne2 .

Note that (ugly=eq1)^(ugly≠ne1) but ugly=eq2 as well, even though eq2 is further away from ugly than ne1 .

Prior to the change in the definition, the following could be observed:

   ∇ foo;⎕ct;⎕io;x
[1]  ⎕ct←0 ⋄ ⎕io←0
[2]  x←1+(⌽1↓(¯2×⍳10)×16*¯14),(2×⍳10)×16*¯13 
                          ⍝ admittedly strange
[3]  ⎕←⊖'.○'[x∘.=x]
   ∇

See Figure 1.

      foo
..................○
.................○.
................○..
...............○...
..............○....
.............○.....
............○......
...........○.......
..........○........
..○○○○○○○○.........
........○○.........
.......○.○.........
......○..○.........
.....○...○.........
....○....○.........
...○.....○.........
..○......○.........
.○.................
○..................

        Figure 1
 

6)  It should be stressed that only comparisons between values that are on the brink of equality are affected. Essentially, a rather fuzzy border has been altered slightly so that, while still fuzzy, it is at least straight.

Implications of ⎕ct←0

1) 

It is obvious from the new definition of tolerant comparison that setting ⎕ct←0 yields exact mathematical relational functions.

      (|a-b)≤⎕ct×(|a)⌈|b
      (|a-b)≤0×(|a)⌈|b
      (|a-b)≤0     equal if and only if a=b
2)  APL interpreter performance is improved, due to the utilization of more efficient algorithms. For most affected functions the improvement is measurable but not significant. For dyadic epsilon, certain inner products (^.= , ∨.≠) and dyadic iota, the improvement can be considerable.
 
3) 

User functions that attempt to be exact (rounding functions are a common example) can be written in a more obvious manner:

Rounding Functions

   ∇ r←rnd1 a
[1]  r←⌊.5+a
   ∇

This function fails because is fuzzed and ⌊.5+3.4999999 might produce 4 as a result.

   ∇ r←rnd2 a
[1]  r←⌊(.5+a)-1|.5+a
   ∇

This works, regardless of the setting of ⎕ct , but is a bit obscure. (Function, courtesy of Doug Forkes)

⎕ct←0 allows use of the obvious rounding function again.

   ∇ r←rnd3 a;⎕ct
[1]  ⎕ct←0 ⋄ r←⌊.5+a
   ∇
4)  Searching

Users frequently encode search arguments as floating point numbers, and use dyadic iota to search a catalog. In such a search exact comparison is absolutely necessary. The following function not only achieves exact comparison, but runs (assuming both arguments have many elements) considerably faster than with ⎕ct≠0 .

   ∇ r←a exactiota b;⎕ct
[1]  ⎕ct←0 ⋄ r←a⍳b	
   ∇




Appendix 1

APL Comparison Tolerance

R.H. Lathwell
IBM APL Design, Philadelphia

Introduction

An important aspect of the original implementation of APL\360 was the treatment of arithmetic functions as abstract functions defined on the continuous set of real numbers [1,2]. This had various consequences, including automatic conversion between different machine representations of numbers so that storage and other aspects of System/360 architecture could be used efficiently while suppressing its details [2].

“Fuzzy” comparisons were introduced so that the actual discrete, fixed-precision, hexadecimal representation could be partly disguised: for example, a comparison between 7 and +/10⍴0.7 should regard the two values as equal. (0.7 cannot be exactly represented as a hexadecimal fraction, and the difficulty can be observed on an IBM System/370 APL system by displaying 7-+/10⍴0.7).

The technique used in the original implementation was to regard numbers whose difference was zero in the first twelve (of fourteen) hexadecimal digits to be equal. The definitions in [3] was developed by M.A. Jenkins and R.H. Lathwell in 1968 when it was found that, for some values, implications for relational functions such as b>a ←→ ~b≤a were violated. It was later discovered that these definitions did not completely correct the difficulty, and when APL system variables were introduced [4], the tolerant functions were rederived, resulting in the definitions given here.
 

Approximate Functions

Computer arithmetic functions (addition, subtraction, multiplication and division) are approximations: The set of real numbers is represented by a set of discrete numbers and the functions map arguments chosen from this set to range members which are closest to the abstract results. Because the values produced by two expressions related by an identity might not be identical, a primitive form of tolerant comparison is required to make common identities hold.

The notion of comparing numbers in mathematics arises in several guises, as in the idea that a sequence of numbers b[1], b[2], … may approach some limiting value a . This is normally defined in terms of whether b belongs to some neighborhood of a . The neighborhood is in turn defined in terms of a radius about a .

In order to make comparison symmetric in the two arguments for equality and inequality, the function which determines the radius must depend on both arguments a and b ; to allow control of the tolerance, it must also depend on a comparison tolerance value.

The implemented relational functions (<,≤,=,≥,>,≠) are approximations and use the value of the system variable ⎕ct (for comparison tolerance) as a parameter, as do inverse indexing and membership (dyadicand) because of the implied comparison, and floor and ceiling because of the implied comparison to integers.

In the following discussion, APL primitive symbols such asdenote exact algebraic functions, while names such as tne are used to denote tolerant functions. Function definitions are given in the form f:⍺+⍵ ; the colon separates the name of the function from the expression which defines it. The special symbolsandrepresent the left and right arguments, respectively, of a dyadic function. Either symbol can be used as the argument of a monadic function. [5]

The dependence on ⎕ct of the radius of the neighborhood may as well be linear, and to make the notion of tolerant comparison the practical one commonly used, for example, in engineering, it should also be a function of the magnitudes of the comparands. The following definition is therefore adopted for the radius function rct (Relative Comparison Tolerance):

      rct:⎕ct×⍺ f ⍵ ,
where f is a non-negative valued function of the magnitudes of its arguments.
 

Tolerance Relations

Using the radius function, rct , the relational functions are defined to take into consideration the neighborhood of equality.

Consider the following identity:

      a≠b ←→ 0≠a-b
          ←→ 0<|a-b

Tolerant inequality must exclude the neighborhood of equality, and hence can be defined as:

      tne:(⍺ rct ⍵)<|⍺-⍵

Similarly, tolerant greater must exclude the neighborhood, that is, a>b ←→ 0>b-a , and therefore tgt:(⍺ rct ⍵)<⍺-⍵ .

Substituting for rct :

      a tne b ←→ (a rct b)<|a-b
              ←→ 0<(|a-b)-a rct b
              ←→ 0<(|a-b)-⎕ct×a f b
              ←→ (a f b)<(|b-a)÷⎕ct  (⎕ct≠0)

and a f b is bounded by (|a)⌈|b .

This bound is, in fact, a satisfactory function and:

      f:(|⍺)⌈|⍵

and therefore rct:⎕ct×(|⍺)⌈|⍵ , and symmetry is assured by the commutativity of . Tolerant inequality then becomes

      tne:0<(|⍺-⍵)-⎕ct×(|⍺)⌈|⍵

A neighborhood of radius ⎕ct×(|a)⌈|b is defined, and a and b are unequal if one is not contained within this neighborhood about the other.

Tolerant inequality can be expressed in terms of functions which are independent of f as follows:

      a tne b ←→ 0<(|a-b)-⎕ct×(|a)⌈|b
              ←→ 0⌈×(|a-b)-⎕ct×(|a)⌈|b

and

      a tgt b ←→ 0<(a-b)-⎕ct×(|a)⌈|b
              ←→ 0⌈×(a-b)-⎕ct×(|a)⌈|b

In order to ensure that the relational functions satisfy their fundamental identities, the remaining four functions are defined in terms of tne and tgt .

      teq:~⍺ tne ⍵     (Tolerant Equality)
 tle:~⍺ tgt ⍵ (Tolerant Not Greater)
 tlt:(⍺ tne ⍵)^~⍺ tgt ⍵ (Tolerant Less Than)
 tge:(⍺ tgt ⍵)^~⍺ tne ⍵ (Tolerant Not Less)

Tolerant Floor and Ceiling

The fundamental identities which floor and ceiling must satisfy are:

      (⌊a)≤a
      (⌈a)≥a
      (⌊a)=-⌈-a

Substituting tolerant relational functions, these become:

      (tfl a)tle a
      (tcl a)tge a
      (tfl a)teq-tcl-a

If tolerant floor (tfl) is expressed in terms of the abstract function as tfl a ←→ ⌊a+g a , and tolerant ceiling as tcl a ←→ ⌈a-g a , where g is a measure of the error and depends on ⎕ct , and the appropriate substitutions made, then

      (g a)≤⎕ct×|a

and, using the upper bound,

      tfl:⌊⍵+⎕ct×|⍵
      tcl:⌈⍵-⎕ct×|⍵

In the above, for sufficiently large values of ⎕ct and |a , there are several integers which will satisfy the tolerant relations. If tolerant floor and ceiling are constrained so that the result is an integer adjacent to a , then

      ((tfl a)=⌊a)∨(tfl a)=⌈a

Applying this additional constraint results in

      tfl:⌊⍵+⎕ct×1⌊|⍵
      tcl:⌈⍵-⎕ct×1⌊|⍵
      and ⎕ct<1

Note that, in effect, an upper bound for ⎕ct is established.
 

Discussion

The functions tne, tgt, teq, tge, tlt, tle, tfl, and tcl are approximations to the mathematical functions ≠, >, =, ≥, <, ≤, ⌊, and . They use the value of ⎕ct to determine a neighborhood of equality. When ⎕ct=0 , the approximations become the exact functions.

Absolute comparison, independent of ⎕ct , can also be obtained by comparisons with zero:

      a tne 0 ←→ 0<(|a-0)-⎕ct×(|a)⌈0
              ←→ 0<(|a)×1-⎕ct
              ←→ a≠0

When ⎕ct>0 , the tolerant functions lose the property of transitivity, and algebraic relations which depend on this property cannot be used. For example, a tne b ←→ (a+c) tne b+c does not hold (consider c=-a).

The intransitivity of equality is well known in practical situations and can be easily demonstrated by sawing several pieces of wood of equal length. In one case, use the first piece to measure subsequent lengths; in the second case, use the last piece cut to measure the next. Compare the lengths of the two final pieces.

Large values of ⎕ct cause the tolerant functions to yield results which are mathematically consistent but which are, to some extent, counter-intuitive. This generally happens when the neighborhood of equality about an integer includes an adjacent integer:

      a teq a+1 ←→ ~a tne a+1
                ←→ (⎕ct×|a+1)≥i
                ←→ (|a+1)≥÷⎕ct    (⎕ct≠0)

so that for any particular non-zero value of ⎕ct , adjacent integers greater in magnitude than ÷⎕ct will be equal. For small values of ⎕ct , tolerant functions yield intuitively correct results in cases where the exact result is not (7=+/10⍴0.7).

⎕ct can, as was the “fuzz” in APL\360, be regarded as a measure of the number of significant digits (approximately ÷⎕ct decimal digits) to which numbers must agree in order to be considered equal. In general, ⎕ct should be chosen to be the smallest value which is large enough to mask common arithmetic errors.
 

Acknowledgment

D.L. Orth provided many useful suggestions in the course of discussion and careful review of the derivations.
 

References

1.  L.M. Breed and R.H. Lathwell, Implementation of APL\360, Symposium on Interactive Systems for Experimental Applied Mathematics, eds., M. Klerer and J. Reinfelds, Academic Press, New York, 1968.
2.  A.D. Falkoff and K.E. Iverson, The APL\360 Terminal System, Research Report RC-1922, IBM, 1967-10-16.
3.  R.H. Lathwell and J.E. Mezei, A Formal Description of APL, Colloque APL, Institut de Recherche d’Informatique et d’Automatique, Rocquencourt, France, 1971.
4.  A.D. Falkoff and K.E. Iverson, The Design of APL, IBM Journal of Research and Development, Volume 17, Number 4, July 1973.
5.  K.E. Iverson, Elementary Analysis, APL Press, Swarthmore, 1976.



First appeared as SHARP APL Technical Note 23, Comparison Tolerance, 1977-06-10; revision 1, 1978-07-15. Appendix 1 first appeared in the APL76 Conference Proceedings.

created:  2009-07-20 12:00
updated:2018-06-19 18:35