2,958
edits
Comparison tolerance: Difference between revisions
Jump to navigation
Jump to search
Be more precise in using "tolerant comparison" versus "comparison tolerance"
m (Adám Brudzewsky moved page Tolerant comparison to Comparison tolerance: swapping ct and tc) |
(Be more precise in using "tolerant comparison" versus "comparison tolerance") |
||
| 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 == | ||