Comparison tolerance: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
m (Naming of "fuzz")
(Be more precise in using "tolerant comparison" versus "comparison tolerance")
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
'''Tolerant comparison''' is an inexact form of [[comparison]] used to mitigate the impact of floating-point rounding error on programs. It considers two [[number]]s equal when their relative difference is smaller than a parameter called the '''comparison tolerance''', and accessed with the [[system variable]] <syntaxhighlight lang=apl inline>⎕CT</syntaxhighlight>. In addition to the comparison functions, tolerance applies to [[Match]] and [[Not Match]], [[Floor]], [[Ceiling]], and [[Modulus]], and [[search function]]s defined in terms of Match (not [[Interval Index]]).
{{Built-in|Comparison tolerance|⎕CT}} is the parameter governing '''tolerant comparison''', an inexact form of [[comparison]] used to mitigate the impact of floating-point rounding error on programs. Two [[number]]s are considered equal when their relative difference is smaller than the comparison tolerance, which is accessed with the [[system variable]] <syntaxhighlight lang=apl inline>⎕CT</syntaxhighlight>. In addition to the comparison functions, tolerance applies to [[Match]] and [[Not Match]], [[Floor]], [[Ceiling]], and [[Modulus]], and [[search function]]s defined in terms of Match (not [[Interval Index]]).


{{quote|In an early talk Ken was explaining the advantages of tolerant comparison. A member of the audience asked incredulously, "Surely you don't mean that when <nowiki>A=B and B=C</nowiki>, A may not equal C?" Without skipping a beat, Ken replied, "Any carpenter knows that!" and went on to the next question.|—Paul Berry<ref>[[Roger Hui]]. [https://keiapl.org/anec/ Ken Iverson Quotations and Anecdotes]. 2005-09-30.</ref>}}
{{quote|In an early talk Ken was explaining the advantages of tolerant comparison. A member of the audience asked incredulously, "Surely you don't mean that when <nowiki>A=B and B=C</nowiki>, A may not equal C?" Without skipping a beat, Ken replied, "Any carpenter knows that!" and went on to the next question.|—Paul Berry<ref>[[Roger Hui]]. [https://keiapl.org/anec/ Ken Iverson Quotations and Anecdotes]. 2005-09-30.</ref>}}


The rule for comparison tolerance is that numbers <syntaxhighlight lang=apl inline>a</syntaxhighlight> and <syntaxhighlight lang=apl inline>b</syntaxhighlight> are equal when
The rule for tolerant comparison is that numbers <syntaxhighlight lang=apl inline>a</syntaxhighlight> and <syntaxhighlight lang=apl inline>b</syntaxhighlight> are equal when
<syntaxhighlight lang=apl>(|a-b) ≤ ⎕CT×(|a)⌈(|b)</syntaxhighlight>
<syntaxhighlight lang=apl>(|a-b) ≤ ⎕CT×(|a)⌈(|b)</syntaxhighlight>
where <syntaxhighlight lang=apl inline>≤</syntaxhighlight> is evaluated intolerantly. This means that the allowed difference between the numbers increases as they become larger in magnitude (a relative tolerance). Comparison with zero is intolerant: only zero can equal zero. A typical value for <syntaxhighlight lang=apl inline>⎕CT</syntaxhighlight> is <syntaxhighlight lang=apl inline>1e¯14</syntaxhighlight>, which is usually large enough to accomodate multiple iterations of double-precision rounding (which introduces error on the order of <syntaxhighlight lang=apl inline>1e¯16</syntaxhighlight>) while being far smaller than typical precision of real-world measurements.
where <syntaxhighlight lang=apl inline>≤</syntaxhighlight> is evaluated intolerantly. This means that the allowed difference between the numbers increases as they become larger in magnitude (a relative tolerance). Comparison with zero is intolerant: only zero can equal zero. A typical value for <syntaxhighlight lang=apl inline>⎕CT</syntaxhighlight> is <syntaxhighlight lang=apl inline>1e¯14</syntaxhighlight>, which is usually large enough to accomodate multiple iterations of double-precision rounding (which introduces error on the order of <syntaxhighlight lang=apl inline>1e¯16</syntaxhighlight>) while being far smaller than typical precision of real-world measurements.


Comparison tolerance was available in some form since [[APL\360]], where it was described as a "fuzz" (on the suggestion of [[Larry Breed]]<ref>[[Adin Falkoff]], and [[Ken Iverson]]. [https://dl.acm.org/doi/abs/10.1145/960118.808372 ''The Evolution of APL''] ([https://www.jsoftware.com/papers/APLEvol.htm web]). ACM SIGPLAN Notices, Volume 13, Number 8. 1978-08.</ref>) applied to some functions. The value <syntaxhighlight lang=apl inline>⎕CT</syntaxhighlight> to control it was defined with the introduction of [[system variable]]s in [[APL.SV]]. The formula now used for comparison tolerance was proposed by [[Dick Lathwell]] in 1976<ref>[[Dick Lathwell]]. [https://doi.org/10.1145/800114.803685 APL comparison tolerance] at [[APL76]] (also reproduced in [https://www.jsoftware.com/papers/satn23.htm SATN-23]).</ref> and later introduced in [[SHARP APL]] by [[Robert Bernecky]] and others<ref>[[Robert Bernecky]]. [https://www.jsoftware.com/papers/satn23.htm "Comparison Tolerance"]. SATN-23. 1977-06-10.</ref> and included in the extended APL standard [[ISO/IEC 13751:2001]].<ref>[[Adin Falkoff]] and D. L. Orth. [https://doi.org/10.1145/800137.804495 "Development of an APL standard"] at [[APL79]].</ref> However, comparison tolerance is not supported in many newer APLs such as [[ngn/apl]], [[dzaima/APL]], and [[Kap]].
Comparison tolerance was available in some form since [[APL\360]], where it was described as a "fuzz" (on the suggestion of [[Larry Breed]]<ref>[[Adin Falkoff]], and [[Ken Iverson]]. [https://dl.acm.org/doi/abs/10.1145/960118.808372 ''The Evolution of APL''] ([https://www.jsoftware.com/papers/APLEvol.htm web]). ACM SIGPLAN Notices, Volume 13, Number 8. 1978-08.</ref>) applied to some functions. The value <syntaxhighlight lang=apl inline>⎕CT</syntaxhighlight> to control it was defined with the introduction of [[system variable]]s in [[APL.SV]]. The formula now used for tolerant comparison was proposed by [[Dick Lathwell]] in 1976<ref>[[Dick Lathwell]]. [https://doi.org/10.1145/800114.803685 APL comparison tolerance] at [[APL76]] (also reproduced in [https://www.jsoftware.com/papers/satn23.htm SATN-23]).</ref> and later introduced in [[SHARP APL]] by [[Robert Bernecky]] and others<ref>[[Robert Bernecky]]. [https://www.jsoftware.com/papers/satn23.htm "Comparison Tolerance"]. SATN-23. 1977-06-10.</ref> and included in the APL standard [[ISO 8485:1989]].<ref>[[Adin Falkoff]] and D. L. Orth. [https://doi.org/10.1145/800137.804495 "Development of an APL standard"] at [[APL79]].</ref> However, tolerant comparison is not supported in many newer APLs such as [[ngn/apl]], [[dzaima/APL]], and [[Kap]].


The application of comparison tolerance to [[search function]]s presents problems for standard hash-based search methods.<ref>[[Roger Hui]]. [https://www.jsoftware.com/papers/Hashing.htm "Hashing for Tolerant Index-Of"] at [[Dyalog '10]].</ref><ref>[[Roger Hui]]. "Tolerant Unique" ([https://www.dyalog.com/uploads/conference/dyalog17/presentations/D10_Tolerant_Unique.zip materials (1.5 MB)], [https://dyalog.tv/Dyalog17/?v=fPWky9IOG40 video (27 mins)]) at [[Dyalog '17]].</ref>
The application of non-zero comparison tolerance to [[search function]]s presents problems for standard hash-based search methods.<ref>[[Roger Hui]]. [https://www.jsoftware.com/papers/Hashing.htm "Hashing for Tolerant Index-Of"] at [[Dyalog '10]].</ref><ref>[[Roger Hui]]. "Tolerant Unique" ([https://www.dyalog.com/uploads/conference/dyalog17/presentations/D10_Tolerant_Unique.zip materials (1.5 MB)], [https://dyalog.tv/Dyalog17/?v=fPWky9IOG40 video (27 mins)]) at [[Dyalog '17]].</ref> Many algorithms can be sped up by setting <syntaxhighlight lang=apl inline>⎕CT←0</syntaxhighlight>, thus disabling tolerant comparison.


== External links ==
== External links ==

Latest revision as of 13:30, 26 February 2024

⎕CT

Comparison tolerance (⎕CT) is the parameter governing tolerant comparison, an inexact form of comparison used to mitigate the impact of floating-point rounding error on programs. Two numbers are considered equal when their relative difference is smaller than the comparison tolerance, which is accessed with the system variable ⎕CT. In addition to the comparison functions, tolerance applies to Match and Not Match, Floor, Ceiling, and Modulus, and search functions defined in terms of Match (not Interval Index).

In an early talk Ken was explaining the advantages of tolerant comparison. A member of the audience asked incredulously, "Surely you don't mean that when A=B and B=C, A may not equal C?" Without skipping a beat, Ken replied, "Any carpenter knows that!" and went on to the next question.

—Paul Berry[1]

The rule for tolerant comparison is that numbers a and b are equal when 

(|a-b) ≤ ⎕CT×(|a)⌈(|b)

where ≤ is evaluated intolerantly. This means that the allowed difference between the numbers increases as they become larger in magnitude (a relative tolerance). Comparison with zero is intolerant: only zero can equal zero. A typical value for ⎕CT is 1e¯14, which is usually large enough to accomodate multiple iterations of double-precision rounding (which introduces error on the order of 1e¯16) while being far smaller than typical precision of real-world measurements.

Comparison tolerance was available in some form since APL\360, where it was described as a "fuzz" (on the suggestion of Larry Breed[2]) applied to some functions. The value ⎕CT to control it was defined with the introduction of system variables in APL.SV. The formula now used for tolerant comparison was proposed by Dick Lathwell in 1976[3] and later introduced in SHARP APL by Robert Bernecky and others[4] and included in the APL standard ISO 8485:1989.[5] However, tolerant comparison is not supported in many newer APLs such as ngn/apl, dzaima/APL, and Kap.

The application of non-zero comparison tolerance to search functions presents problems for standard hash-based search methods.[6][7] Many algorithms can be sped up by setting ⎕CT←0, thus disabling tolerant comparison.

External links

Documentation

References

  1. ↑ Roger Hui. Ken Iverson Quotations and Anecdotes. 2005-09-30.
  2. ↑ Adin Falkoff, and Ken Iverson. The Evolution of APL (web). ACM SIGPLAN Notices, Volume 13, Number 8. 1978-08.
  3. ↑ Dick Lathwell. APL comparison tolerance at APL76 (also reproduced in SATN-23).
  4. ↑ Robert Bernecky. "Comparison Tolerance". SATN-23. 1977-06-10.
  5. ↑ Adin Falkoff and D. L. Orth. "Development of an APL standard" at APL79.
  6. ↑ Roger Hui. "Hashing for Tolerant Index-Of" at Dyalog '10.
  7. ↑ Roger Hui. "Tolerant Unique" (materials (1.5 MB), video (27 mins)) at Dyalog '17.
APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic Conjugate ∙ Negate ∙ Signum ∙ Reciprocal ∙ Magnitude ∙ Exponential ∙ Natural Logarithm ∙ Floor ∙ Ceiling ∙ Factorial ∙ Not ∙ Pi Times ∙ Roll ∙ Type ∙ Imaginary ∙ Square Root ∙ Round
Dyadic Add ∙ Subtract ∙ Times ∙ Divide ∙ Residue ∙ Power ∙ Logarithm ∙ Minimum ∙ Maximum ∙ Binomial ∙ Comparison functions ∙ Boolean functions (And, Or, Nand, Nor) ∙ GCD ∙ LCM ∙ Circular ∙ Complex ∙ Root
Non-Scalar
Structural Shape ∙ Reshape ∙ Tally ∙ Depth ∙ Ravel ∙ Enlist ∙ Table ∙ Catenate ∙ Reverse ∙ Rotate ∙ Transpose ∙ Raze ∙ Mix ∙ Split ∙ Enclose ∙ Nest ∙ Cut (K) ∙ Pair ∙ Link ∙ Partitioned Enclose ∙ Partition
Selection First ∙ Pick ∙ Take ∙ Drop ∙ Unique ∙ Identity ∙ Stop ∙ Select ∙ Replicate ∙ Expand ∙ Set functions (Intersection ∙ Union ∙ Without) ∙ Bracket indexing ∙ Index ∙ Cartesian Product ∙ Sort
Selector Index generator ∙ Grade ∙ Index Of ∙ Interval Index ∙ Indices ∙ Deal ∙ Prefix and suffix vectors
Computational Match ∙ Not Match ∙ Membership ∙ Find ∙ Nub Sieve ∙ Encode ∙ Decode ∙ Matrix Inverse ∙ Matrix Divide ∙ Format ∙ Execute ∙ Materialise ∙ Range
Operators Monadic Each ∙ Commute ∙ Constant ∙ Replicate ∙ Expand ∙ Reduce ∙ Windowed Reduce ∙ Scan ∙ Outer Product ∙ Key ∙ I-Beam ∙ Spawn ∙ Function axis ∙ Identity (Null, Ident)
Dyadic Bind ∙ Compositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner Product ∙ Determinant ∙ Power ∙ At ∙ Under ∙ Rank ∙ Depth ∙ Variant ∙ Stencil ∙ Cut ∙ Direct definition (operator) ∙ Identity (Lev, Dex)
Quad names Index origin ∙ Comparison tolerance ∙ Migration level ∙ Atomic vector
Retrieved from ‘https://aplwiki.com/index.php?title=Comparison_tolerance&oldid=11084’