[NumericPrelude] GCD as monoid

[Paul McJones]

Henning,

I don't quite see where you're headed with this proposal. If the problem 
of units is complicating things, would it be useful to define a 
semigroup rather than a monoid?


Paul


On 7/3/10 1:47 PM, Henning Thielemann wrote:
> 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.
>
> _______________________________________________
> Numeric-Prelude mailing list
> Numeric-Prelude at projects.haskell.org
> http://projects.haskell.org/cgi-bin/mailman/listinfo/numeric-prelude
>