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

*To*: Greenwald@STONY-BROOK.SCRC.Symbolics.COM, 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*: Scott Cyphers <Cyphers@YUKON.SCRC.Symbolics.COM>*Date*: Thu, 26 Mar 87 14:58 EST*Cc*: Numerics@STONY-BROOK.SCRC.Symbolics.COM*In-reply-to*: <870326133440.1.GREENWALD@SWALLOW.S4CC.Symbolics.COM>

Date: Thu, 26 Mar 87 13:34 EST From: Michael Greenwald <Greenwald@STONY-BROOK.SCRC.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.) Leave things the way they are. You're trying to give too much meaning to something which only derives its meaning from the way it is being used. In normal situations, things behave about how you'd expect them to. It is only when you get into the noise that things fall apart, because the multiple interpretations are no longer distinct. In those cases, I say it is an error to write something like (< x rational), and that you have no right to expect something like transitivity to hold because you're mixing definitions. If you want to say <, then do the coercions yourself in the way appropriate to what your working on. Rationals aren't necessarily any more exact than floating point. If you're computing rationals, then they're exact, but if you're computing reals, then they're no more exact than floating point. What if someone is trying to say (< x (sqrt 2))? Unless they are doing their own coercions (or squaring x) I think there's always going to be some form of default coercion which will do the "unexpected" for them.

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

- Prev by Date:
**Numerical Comparison: "required coercions"** - Next by Date:
**Re: Numerical Comparison: "required coercions"** - Previous by thread:
**Numerical Comparison: "required coercions"** - Next by thread:
**Numerical Comparison: "required coercions"** - Index(es):