SATN-23 Abstract The definition of tolerant comparison used in SHARP APL has been changed. This SATN describes the justification for and effects of that change.
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.
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,
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
Implications of ⎕ct←0
Appendix 1 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 (dyadic ⍳ and ∊) because of the implied comparison, and floor and ceiling because of the implied comparison to integers. In the following discussion, APL primitive symbols such as ≠ denote 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 symbols ⍺ and ⍵ represent 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 .
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
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.
|