GCD for Euclidean rings

From: helmut.zeisel_at_[hidden]
Date: 2001-10-10 15:17:37

Since there might be some confusion
what I understand by
a "generalization" of the Euclidean algorithm
used in GCD,
I want to give a more complete code example.

An implementation could be like the following
(my example is based on the gcd version in rational.hpp,
a similar adaption can be done 
for the version in dlw_gcd):

namespace helmut
{
template <typename IntType>
IntType gcd(IntType n, IntType m)
{
   IntType zero(0);

   for(;;) {
      if(m == zero)
        return n;
      n %= m;
      if(n == zero)
        return m;
      m %= n;
    }
}
};

Please observe:

1) It is easy to show that
the algorithm converges for integral m,n
even when one does
not make any special assumption about
the sign of m%n (which is not defined by the standard)
when one of the operands is negative.

2) The algorithm is simpler and
needs less assumptions than the original 
implementation
(in particular, we only need
operator== for comparision, and no other comparision operator).

3) For integral m,n >= 0 we obtain the same results:

helmut::gcd(m,n) == boost::gcd(m,n)

4) If m or n is negative, the sign
of the result is "implementation dependent";
we have, however,

abs(helmut::gcd(m,n)) == boost::gcd(m,n)

5) If one is worried about the sign,
it is easy to implement the current
behavior of boost::gcd using the
more general implementation:

Version a)

boost::gcd(m,n) = helmut::gcd(abs(m),abs(n))

This version is equivalent to the current implementation.

Version b)

boost::gcd(m,n) = abs(helmut::gcd(m,n))

This version needs only one abs
and is (slightly) more efficient than
the current implementation.

6) Using traits or some similar technique,
and an implementation of boost::gcd
calling helmut::gcd (like in 5),
it is possible to offer both interfaces,
so that clients can choose a suitable
version for their type.

Helmut