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

*To*: cl-cleanup@sail.stanford.edu*Subject*: Issue: MULTIPLICATION-ZERO-ARGS*From*: Guy Steele <gls@Think.COM>*Date*: Fri, 28 Apr 89 18:16:19 EDT*Cc*: gls@Think.COM

Issue: MULTIPLICATION-ZERO-ARGS References: CLtl p. 199 Category: CHANGE Edit history: Version 1 by Guy Steele 04/28/89 Problem Description: This function is not well-defined for sets of arguments that include the number zero. Proposal (MULTIPLICATION-ZERO-ARGS:NOT-ALLOWED): Integer arguments to * must be non-zero. Test Case: (* 1 0) would be an error instead of having the value 0. Rationale: Having the product of a set of integers be less than the product of a proper subset of that set violates monotonicity. For example, monotonicity is violated by (* 6 0) < (* 6) and (* 0) < (*). The multiset of prime factors of a product is the union of the multisets of prime factors of the numbers being multiplied. Increasing the multiset of prime factors that contribute to the result should only be able to increase the value of result. What the first example is saying is that the multiset of factors of 6 has two elements {2, 3} but the product of both 6 and 0 does not. This is patently ridiculous. Any reasoning that says that 0 is the product of 6 & 0 would also say that 0 is the product of 6 alone, since 0 has all the prime factors that 6 does and is the smallest such number. Furthermore, it would say that 0 is the result of the multiplication operation on any set of arguments at all. Although this would be mathematically consistent, it would not make multiplication a very useful operator. The root of the problem is that it is unnatural to apply multiplication to anything but natural numbers. Multiplication over the positive integers forms a monoid, and over the rational numbers forms a group. Negative numbers do not have much of an effect because they can be treated as if they were their absolute values, with signs handled separately, but zero really screws things up. If it is desired that zero be an allowed argument, it should also just be ignored, (i.e passed over, the way nil in an association list is passed over) Current Practice: I know of no implementations that currently implement this change. Cost to Users: Very slight. Cost to Implementors: Very slight. Should lead to a reduction in code, since most algorithms for computing products are for positive integers anyway. (Consider what you learned in second grade.) Benefits: see Esthetics. Esthetics: Mathematical correctness is much more aesthetic than its alternatives. Discussion: This is not a satire. Skona's arguments about LCM are correct, and my arguments about multiplication are of exactly the same form. Zero really does screw up multiplication. If it were not for addition, the value of zero to addition, and the relationship of addition to multiplication (especially through the distributive law), we would not put up with zero. If you formulate multiplication in terms of unions of multisets of prime factors (a natural and convenient representation for integers if you don't have to do addition), then there isn't even any good representation for zero. But addition and zero ARE important, so we agree to extend the range of multiplication to include zero, even though it has weird properties like destroying the invertibility of multiplication (suddenly (/ (* A B) B) is not always equal to A). The same holds for GCD and LCM. Yes, their behaviors for arguments that are zero is weird and makes no sense. But we adopt these definitions anyway because they preserve useful identities. For example, we have the identity (* x (gcd y z)) = (gcd (* x y) (* x z)) If x is zero, then we had better have (gcd 0 0) = 0. If y is zero, then we have (* x (gcd 0 z)) = (gcd 0 (* x z)) and letting (gcd 0 a) = a is the simplest way of preserving this. Then consider (* u v) = (* (gcd u v) (lcm u v)) Let u be zero. Then to preserve this identity at least one of (gcd u v) and (lcm u v) must be zero. But (gcd 0 v) = v, so if v is not zero then (lcm 0 v) had better be zero. See Knuth, volume 2, section 4.5.2. There you will see that he finds it convenient to use the prime-factor representation of integers to explain gcd and lcm (and in fact during that part of the discussion he conveniently ignores the fact that you cannot encode zero in that representation--and for his expository purposes it doesn't matter). So that is why gcd and lcm behave in such strange ways: they preserve important identities in the boundary cases. A cardinal rule of mathematics is that consistency is more important than making sense. (In fact, consistency is the *definition* of making sense.) So I argue that, whatever we do, we should treat GCD/LCM and multiplication on integers in exactly the same way. Either all accept arguments that are zero, or none do.

- Prev by Date:
**ISSUE: GCD-LCM-ZERO-ARGS** - Next by Date:
**[chapman%aitg.DEC@decwrl.dec.com: question @ SUBTYPEP-TOO-VAGUE]** - Previous by thread:
**ISSUE: GCD-LCM-ZERO-ARGS** - Next by thread:
**[chapman%aitg.DEC@decwrl.dec.com: question @ SUBTYPEP-TOO-VAGUE]** - Index(es):