Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at