gcd 0 0 = 0

Kent Karlsson kentk@md.chalmers.se
Tue, 18 Dec 2001 18:00:30 +0100


> >>>>> "Simon" == Simon Peyton-Jones <simonpj@microsoft.com> writes:
> 
>     Simon> Christoph does not like this

I still don't like this.  0 has never, and will never, divide anything,
in particular not 0.  0 may be a prime factor of 0 (see also below!),
but that is different. It is not the greatest (in the ordinary sense)
divisor of 0.  Indeed, +infinity is a much larger divisor of 0...

I'm not in favour of using a very special-purpose order, not used for
anything else, and that isn't even an order but a preorder, just to
motivate gcd 0 0 = 0.  Even if using this very special-purpose preorder,
an infinity would be included in the 'top' equivalence class, and if we
pick a representative value on the basis of which is 'greater' in the
ordinary sense for integers augmented with infinities(!), then +infinity
should be the representative value.  Thus, in any case, gcd 0 0 = +infinity.

This is easy enough for Integer, where +infinity and -infinity can easily
be made representable (and should be made representable), but harder for
a 'pure hardware' Int datatype.  But in an ideal world, gcd 0 0 = +infinity
with no error or exception.

> It's OK if the definition is clear; it wasn't using
> the words "positive" or "greatest integer".
> 
> Stating "gcd 0 0 = 0" explicitly is a good thing,
> even if it could be expressed verbatim;
> people may think about the mathematical background,
> but they should not need to think about the
> meaning of the definition.


> Anyway, I'm still against promoting 1 to a prime number :-)

Why?  If EVERY natural number is to have a  prime factorisation, then BOTH
0 AND 1 have to be promoted to prime numbers; otherwise 1 and 0 cannot be
prime factorised; in addition to that 1 is then a prime factor of any number
(that can be excluded from the *minimal* list of prime factors except for 1)...
There is no fundamental reason to except 1 from being a prime number.  But
there is a fundamental reason to say that 0 can never be a divisor (i.e. 0|0
is false; x|y is true iff x is a *non-zero* factor of y; the 'non-zero' part
is often left implicit (e.g. one is only talking about strictly positive
integers), which is part of the reason why we are having this discussion).

If you want something similar to gcd, but that returns 0 for 0 and 0, then
it is the 'product of all common prime factors'; where 1 has the (non-minimal)
prime factorisation [1, 1, ...], 0 has the (non-minimal) prime factorisation
[0, 1, 2, ...], and 1 is included at least once in the (non-minimal) prime
factorisation of any natural number. If you want a parallel to the divides
relation where 0 and 0 are related: 0 is a factor of 0.  A prime number
is a number that has no integer *between* 1 and itself as factors. People
often say "except" instead of "between", but that does not work for 0, nor
for the non-minimal prime factorisations that people seem to be interested
in, given the interest in having gcd 0 0 = 0 (which isn't the gc*d*!). Again,
the context is often strictly positive integers, and 'between' and 'except'
are then equivalent.  For no apparent reason 1 is usually also excepted, but
that does not work for the prime factorisation of 1, nor for finding the
product of all common prime factors of 1 and another natural number... For
integers, -1 is also a prime number, and for imaginary integers, i is also
a prime number...  I'm sure somebody can give a nice definition of a partial
order (not just preorder) lattice with 1 as the min value and 0 as the max
value (just larger than the infinities), if you absolutely want a lattice
with a gcd-*like* meet and lcm-*like* join for this (the, positive bias,
factor-of order).

I'd be happy to support such gcd-*like* (pcf?) and lcm-*like* functions, but
they aren't the gcd, nor the lcm (e.g. pcf (-1) (-1) = -1, not 1, etc.).
If you don't like adding these, then I suggest leaving things completely as
they are.  Squeezing in two operations into one just because they have the
same results over the first quadrant is not something I find to be too good.

		Odd one out?
		/kent k