Some remarks on modulo.cpp

From: Christoph Koegl (yahoo_at_[hidden])
Date: 2001-06-11 08:08:18

Hi (especially to Daryle).

I heard nothing in response to my remarks on rational.cpp so I suppose my remarks must
make either complete sense or be completely off target ;-) I would be interested in
any thoughts, though. Perhaps nobody actually uses rational.cpp? Would be a shame.

Anyway, here are some remarks on modulo.cpp from the files section.

1.
The choice of "Ring" as the main template parameter name is somewhat misleading IMO.
"Modulus" would be more on target and more in accordance with common mathematical
vocabulary. The class template implements some aspects of the rings Z/(n) (or Z/n
for brevity), and most literature refers to n as the modulus.

2.
Let me evilly question the need for such a library. There are proven, efficient lib-
raries out there for the task at hand (GMP, NTL, CLN, libI, Piologie, Pari-GP), and
these were optimized over many years. Why reeinvent some part of these?
As for the many-valued logic functionality: There are many multi-valued logics out
there. What applications are you alluding to in the rationale specifically? You
seem to implement something like Lukasiewicz's many-valued logics. But there are many
more many-valued logics that "behave" differently (i.e. the computation of their
truth values is different). I think the "lumping-together" of concerns (as opposed
to the worthy goal of separation of concerns) needs more justification. Is it just
for "sharing of implementation" purposes as you seem to suggest (you talk about
"[using] similar implementations, [...] so they have been merged to save space").
Perhaps we should have separate classes for modular arithmetic (together with
some ordering functionality, which is only there for being able to store modulo's in
associative containers, right?) and for many-valued logic operations. The m.-v. logic
class then uses the modulo class in its implementation.

3.
I cite from the "Background" part of the docs:
> Modulo arithmetic maps real numbers to classes. Each class represents a remainder
> after division by a chosen ring, a real value.
As the reals are a field, division with remainder is not very interesting (the remain-
der is always zero). Your template parameter is unsigned long. So you really mean
"integer" when you say "real number", don't you?

4.
In your most recent mail to the boost list you say:
> I was considering asking about adding an operator %=, then I  realized
> that a remainder isn't well-defined in modulo arithmetic.   Division
> is just multiplying by the reciprocal, it has no "real"  meaning,
> unlike division with real numbers.
Well, what is "real meaning"? When dividing in any field (and the reals as well as
Z/p for p prime are fields) or in a ring (whenever possible to do so) this really
means "multiplying by the multiplicative inverse." So there is no conceptual differ-
ence in division as we know it from familiar fields like the rationals; division is
possible whenever the divisor in invertible in the ring.
As to division with remainder: If a ring satisfies certain requirements, a division
with remainder that "behaves well" exists. E.g. if we have a Euclidean ring, the
remainder can always be chosen to be "smaller" than the divisor in some well-defined
sense. This enables one to employ the Euclidean GCD algorithm. This does not apply to
Z/n, however: Z/p for p prime is a field, and Z/n for n not prime is not even an
integral domain, i.e. it has zero-divisors (e.g. in Z/6 2 multiplied by 3 "is" zero).
I do not know of any meaningful definition of a "division with remainder" concept in
Z/n. (And in Z/p the remainder is, as I said above, always zero.)

5.
The documentation has still to explain the library's behavior if certain conditions
are not met. What happens if non-invertible values are used where invertible ones
are needed (the implementation throws an exception, as I see)? I think there should
be ways to enable clients to test if these conditions are met, e.g. by some member
function

bool invertible( ) const

that tests for invertibility.

6.
What do we need

template < unsigned long Ring2 > modulo( modulo<Ring2> const &copied );

for? And why should Ring2 be a multiple of Ring? I see that the conversion as imple-
mented assures that the "new" congruence classes are exactly unions of the "old"
equivalence classes. What usage did you have in mind (e.g. what is the rationale for
having exactly this semantics)?

7.
Why do we need static constant member ring when we have template parameter Ring? I
must miss something obvious ... something about compile-time constant expressions?

Cheers, Christoph
-- 
================================================================================
Christoph Koegl, Dept. of Computer Science, University of Kaiserslautern
E-Mail: christoph at familie-koegl dot de
WWW: http://www dot familie-koegl dot de/
--------------------------------------------------------------------------------
There are no stupid questions, but there are a LOT of inquisitive idiots.
--------------------------------------------------------------------------------