Re: Some remarks on modulo.cpp

From: Daryle Walker (darylew_at_[hidden])
Date: 2001-06-12 23:17:05

on 6/11/01 3:08 PM, Christoph Koegl at yahoo_at_[hidden] wrote:

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

It's "modulo.zip," probably at version 2 when you wrote this.

> 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.

The newest version (3) makes this, and other, name changes.

> 2.
> Let me evilly question the need for such a library. There are proven,
> efficient libraries 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.

I'm going for simplicity, not to compete with the professional math
packages.  The author of "rational.hpp" says the same thing about that
package (and I copied that section of the rational package index.html).  I
had bits & pieces of a modulo class lying about for years, but I decided to
finally put it together now.  The multivalued logic was a spur-of-the-moment
thing based on 5 lines I saw in a random Usenet posting.  Instead of having
two small-ish classes, I did the same sort of "abuse" the standard did in
putting arithmetic, bit-wise, and Boolean operations in the built-in
integral classes.

I put in the ordering operators (i.e. "<") for no particular reason.  Hubert
Holin said that modular types don't order well.  However, I thought that you
may want to use ordering for logic states (after all, I use ordering for AND
and OR).  You gave a good reason (to use in associative containers) too.

> 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
> remainder is always zero). Your template parameter is unsigned long. So you
> really mean "integer" when you say "real number", don't you?

I think you can have modulo types with non-integer reals.  The residue would
be the difference between your number and the next-lowest integral multiple
of the modulus.  For instance, if you use four-fifths as the modulus, the
least residues would be in the range [0, 0.8) and the number 1 would map to
0.2 (1 = 1 * 0.8 + 0.2).  I sometimes think of a "rational_modulo.hpp" that
has rational-based modulo types.

> 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 difference 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.)

In real life, division (at least for integers) maps to sectioning an object
into several equal size pieces.  Subtraction means what's left after
removing a part.  Modulo division seems too abstract for that.

> 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.

I did that in version 3.  There is more information on the behavior in the
documentation, and the "is_invertible" member function has been added.

> 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
> implemented 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)?

It doesn't have any real usage.  A lot of class templates provide some way
of cross-conversion among various versions.  I thought I'll allow it, but
make sure that _some_ sort of unique mapping can be done.  The other cross
conversions I block are many-to-many or one-to-many, and we need a
many-to-one here.  (The automatic copy constructor takes care of one-to-one,
since the only modulus multiple that isn't many-to-one is the same-version
construction.)

> 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?

Yeah, you can find the Ring by simply looking at the code, but that won't
help in automation with compile-time constants.  I always try to make
template parameter available through constants or typedef's, in case the
parameters aren't obvious (e.g. the type name is hidden by a typedef).  I
also try to use these constants/typedefs in internal computations, so I
won't have to replace "T"s when I copy & paste a specialization.

-- 
Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com