[NumericPrelude] GCD as monoid
Paul McJones
paul at mcjones.org
Sun Jul 4 16:26:21 EDT 2010
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
>
More information about the Numeric-Prelude
mailing list