2,962
edits
Comparison tolerance: Difference between revisions
Jump to navigation
Jump to search
Be more precise in using "tolerant comparison" versus "comparison tolerance"
(Rework to be CT instead of TC, following the style of IO and ML) |
(Be more precise in using "tolerant comparison" versus "comparison tolerance") |
||
| (One intermediate revision by one other user not shown) | |||
| Line 3: | Line 3: | ||
{{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 | 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 | 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> Many algorithms can be sped up by setting <syntaxhighlight lang=apl>⎕CT←0</syntaxhighlight>, thus disabling tolerant comparison. | 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 == | ||