[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: DCP@QUABBIN.SCRC.Symbolics.COM, gls@Think.COM, Moon@STONY-BROOK.SCRC.Symbolics.COM, Common-Lisp@sail.stanford.edu*Subject*: Numerical Comparison: "required coercions"*From*: Michael Greenwald <Greenwald@STONY-BROOK.SCRC.Symbolics.COM>*Date*: Thu, 26 Mar 87 13:34 EST*Cc*: Numerics@STONY-BROOK.SCRC.Symbolics.COM*In-reply-to*: <870326104752.9.DCP@KOYAANISQATSI.S4CC.Symbolics.COM>

Date: Thu, 26 Mar 87 10:47 EST From: David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM> Date: Thu, 26 Mar 87 10:29 EST From: Guy Steele <gls@Think.COM> This issue makes me want to restate an earlier proposed model for the comparison functions: (? x1 x2 x3 x4 ... xn-1 xn) <=> (AND (? x1 x2) (? x1 x3) (? x1 x4) ... (? x1 xn-1) (? x1 xn) (? x2 x3) (? x2 x4) ... (? x2 xn-1) (? x2 xn) (? x3 x4) ... (? x3 xn-1) (? x3 xn) . . . . . (? xn-1 xn)) where "?" may be =, /=, <, >, <=, or >=. That is, in principle every pair of arguments is compared. This is the model that justifies the "all different" interpretation for /=, and it is recognized that in practice the other five operations may be implemented cleverly through exploitation of transitivity. Well, maybe such reliance on transitivity is wrong. Why "maybe"? (<= 1234d10 12340000000001 1234e10 12340000000000) => T when you depend on transitivity, but should => NIL according to the above model. On the other hand, SORT clearly depends on transitivity, and one might reasonably expect (APPLY '<= (SORT SEQUENCE '<=)) => T. (Or even more reasonably (APPLY '< (SORT SEQUENCE '<)) => T, which unfortunately isn't true since (SORT '(1234d10 12340000000001 1234e10 12340000000000) '<) returns the original sequence.) I'm a fan of transitivity and also recognize this problem. If this is n^2 computation is to be the law-of-the-land for the non /= cases, I would suggest a declaration that tells the compiler that the user is guaranteeing transitivity so that only a linear number of comparisons is needed. The declaration is unnecessary, (although might be useful), since the check for whether transitivity will work can be done in linear time. (This same strategy reduces /= to NlogN for cases where transitivity holds, and all the elements are orderable by sorting the numbers and then only comparing adjacent elements. This doesn't work if any coercions could lose precision. (This works for complex numbers, too)) In practice, our implementation assumes transitivity holds, except in /=, where we are more scrupulous. All these anomolies are solved by coercing to the *most* exact representation for comparisons. I'm assuming that the floating-point contagion rule was mandated for two reasons: (1) It is misleading to *add* bits of precision during a computation. (although this is belied by the single-to-double conversion rule) (2) Floats put a stricter upper bound on the required storage than do the corresponding rationals and bignums. Both of these rules are more applicable for computations (+, -, etc.) than for comparisons. CLtL chose a single coercion rule ("WhenEVER a rational meets a floating point number, the rational is first converted to a floating-point number of the same format") rather than two coercion rules ("In computations that produce new values, the arguments are first coerced to the least precise representation of the two arguments, and the result has the same, imprecise, representation. In comparisons, arguments that differ in type are first converted to the *most* precise representation of the two arguments."). In some sense (although I don't believe this) you might be able to argue that CLtL's decision made the language "simpler", (although it certainly made the results of some of the numeric functions more "surprising"). If it isn't too late, maybe the coercion rule could be changed in the "cleaned up Common Lisp". (Unless someone knows of equally bizarre results of *that* coercion rule.)

**Follow-Ups**:**Numerical Comparison: "required coercions"***From:*Scott Cyphers <Cyphers@YUKON.SCRC.Symbolics.COM>

**Numerical Comparison: "required coercions"***From:*Michael Greenwald <Greenwald@STONY-BROOK.SCRC.Symbolics.COM>

**References**:**Numerical Comparison: "required coercions"***From:*David C. Plummer <DCP@QUABBIN.SCRC.Symbolics.COM>

- Prev by Date:
**Numerical Comparison: "required coercions"** - Next by Date:
**Extension to MAP [if the shoe doesn't fit?]** - Previous by thread:
**Numerical Comparison: "required coercions"** - Next by thread:
**Numerical Comparison: "required coercions"** - Index(es):