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.
> 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
The newest version (3) makes this, and other, name changes.
> 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
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
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.
> 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.
> 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.
> 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.
> 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
> Why do we need static constant member ring when we have template parameter
> Ring? I must miss something obvious ... something about compile-time constant
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk