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


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.


Integer arguments to * must be non-zero.

Test Case:

(* 1 0) would be an error instead of having the value 0.


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.)


see Esthetics.


Mathematical correctness is much more aesthetic than its alternatives.

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

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

	(* 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.