dlw_gcd.zip review

From: wb_at_[hidden]
Date: 2001-09-14 17:23:19

Issue #1:  special case
-----------------------

I have a concern about the way a special case of the gcd algorithm is
handled at the moment.

In common_factor.hpp we currently have:

    // Non-recursive case
    template < unsigned long Value1 >
    struct static_gcd_helper_t< Value1, 0UL >
    {
        BOOST_STATIC_CONSTANT( unsigned long, value = Value1 );
    };

This is generally fine, but not when the template argument is also
0uL.  In this case, the above code would give a result of 0uL -- but
the Euclidean algorithm explicitly requires that not both its inputs be
zero.  (The rationale, perhaps oversimplified, is that no divisor can
meaningfully be zero, since division by 0 is undefined, and no other
answer is correct.)

I respectfully recommend that a specialization, along the following
lines, be inserted to account for this special case and to force the
compiler to issue a diagnostic if user code ever happens to provoke
this situation:

    // Euclidean algorithm excludes this case
    template < >
    struct static_gcd_helper_t< 0uL, 0uL >
    {
      // *** gcd<0,0>::value is explicitly not defined ***
    };

Issue #2:  extension
--------------------

The classic Euclidean algorithm is not defined for negative values.
However, I believe it is a generally useful and straightforward
extension of the algorithm to provide a useful result in such a
circumstance.  Indeed, the supplied run-time function already does so,
it seems; should not the compile-time computation do the same?  (But
see Issue #3 below.)

Issue #3:  question for experts
-------------------------------

This code (as well, I'm sure, as many other programmers' code) uses the
C++ remainder operator % as if it were a mod operator.  Technically, of
course, remaindering is a different operation from taking a modulus.
Does this distinction have any practical significance in the context of
the classical (non-negative) Euclidean algorithm?  (I believe not.)

But what about the case of the extension described above?  Portability
is, of course, the true concern here:  recall that the C++ Standard
describes (5.6/4) only the relationship between the division and
remainder operators, and does not prescribe either in isolation; only a
non-normative footnote refers to a "preferred algorithm for integer
division ... in which the quotient is always rounded toward zero."

If use of remaindering on negative operands is deemed non-portable, then
I would recommend against the extension as described in Issue #2 above,
and also in the library's supplied run-time function, unless a portable
workaround can be provided.

        - WEB