[NumericPrelude] GCD as monoid
Henning Thielemann
lemming at henning-thielemann.de
Sat Jul 3 16:47:56 EDT 2010
Hi Darrell,
Your development of the Unique Factorization Domain remind me on a recent
problem with making a monoid with respect to GCD, see MathObj.Monoid. E.g.
for integers, the identity element should be zero, but how to define 'gcd'
for general types such that
gcd 0 (-1) = -1
and not
gcd 0 (-1) = 1
for the special case of integers?
How to cope with units in general for GCD?
gcd 1 (-1) = -1 ?
gcd 1 (-1) = 1 ?
The problem is that there are multiple GCDs and we have to choose one in a
reasonable way.
Of course, also LCM should be a monoid operation, with identity element 1
in case of integers. That is
lcm 1 (-1) = -1
LCM should be compatible with GCD and should also cope reasonably with
signs. In order to have (lcm x y * gcd x y = x*y), we need to choose:
gcd 1 (-1) = 1
Maybe we should generalize this to
lcm unitA unitB = unitA * unitB
gcd unitA unitB = identity
in case of x and y are relatively prime:
lcm x y = x * y
gcd x y = stdUnit x * stdUnit y
lcm zero x = zero
gcd zero x = x
Maybe this is a convention that works, but I do not know, whether the
result of the Euclidean algorithm can always satisfy these properties.
Applying the Euclidean algorithm only on standard associates may help in
case none of the operands is zero.
More information about the Numeric-Prelude
mailing list