[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