Comparison tolerance

From APL Wiki
Jump to navigation Jump to search

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

APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic ConjugateNegateSignumReciprocalMagnitudeExponentialNatural LogarithmFloorCeilingFactorialNotPi TimesRollTypeImaginarySquare RootRound
Dyadic AddSubtractTimesDivideResiduePowerLogarithmMinimumMaximumBinomialComparison functionsBoolean functions (And, Or, Nand, Nor) ∙ GCDLCMCircularComplexRoot
Non-Scalar
Structural ShapeReshapeTallyDepthRavelEnlistTableCatenateReverseRotateTransposeRazeMixSplitEncloseNestCut (K)PairLinkPartitioned EnclosePartition
Selection FirstPickTakeDropUniqueIdentityStopSelectReplicateExpandSet functions (IntersectionUnionWithout) ∙ Bracket indexingIndexCartesian ProductSort
Selector Index generatorGradeIndex OfInterval IndexIndicesDealPrefix and suffix vectors
Computational MatchNot MatchMembershipFindNub SieveEncodeDecodeMatrix InverseMatrix DivideFormatExecuteMaterialiseRange
Operators Monadic EachCommuteConstantReplicateExpandReduceWindowed ReduceScanOuter ProductKeyI-BeamSpawnFunction axisIdentity (Null, Ident)
Dyadic BindCompositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner ProductDeterminantPowerAtUnderRankDepthVariantStencilCutDirect definition (operator)Identity (Lev, Dex)
Quad names Index originComparison toleranceMigration levelAtomic vector