Design Question

[Ralf Goertz]

Hi,

what would be the best design for a class that represents the ring of
integers modulo some other integer? The problem is it only makes senes
to add, substract etc two such numbers if the belong to the same ring,
i.e. they have the same modulus. First, I thought of something like

typedef unsigned long long Int;

template <Int m> class Zm {
Int v; //value mod m
Zm<m>
Zm<m> & operator+=(Zm<m> r) {
v=(v+r.v)%m;
return *this;
}
...
public:
Zm<m>(const Int _v=Int(0)):v(_v%m) {}
};

With this approach, elements from different rings cannot be used
together in arithmetical operations. But of course, all possible moduli
would need to be known at compile and for each modulus there would be a
separate class.

The other approach would be

class Zm {
Int m,v;
bool valid;
Zm & operator+=(Zm r) {
valid &= (r.valid && (m==r.m));
v=(v+r.v)%m;
return *this;
}
...
public:
Zm(const Int _m, const Int _v):m(_m),v(_v%m),valid(true) {}
};

But this is not very elegant. Is there some better approach? Maybe with
derived classes?

Ralf

 

[Alf P. Steinbach]

* Ralf Goertz:

Hi,

what would be the best design for a class that represents the ring of
integers modulo some other integer? The problem is it only makes senes
to add, substract etc two such numbers if the belong to the same ring,
i.e. they have the same modulus. First, I thought of something like

typedef unsigned long long Int;

template <Int m> class Zm {
Int v; //value mod m
Zm<m>
Zm<m> & operator+=(Zm<m> r) {
v=(v+r.v)%m;
return *this;
}
...
public:
Zm<m>(const Int _v=Int(0)):v(_v%m) {}
};

With this approach, elements from different rings cannot be used
together in arithmetical operations. But of course, all possible moduli
would need to be known at compile and for each modulus there would be a
separate class.

The other approach would be

class Zm {
Int m,v;
bool valid;
Zm & operator+=(Zm r) {
valid &= (r.valid && (m==r.m));
v=(v+r.v)%m;
return *this;
}
...
public:
Zm(const Int _m, const Int _v):m(_m),v(_v%m),valid(true) {}
};

But this is not very elegant. Is there some better approach? Maybe with
derived classes?

Second approach is in general plain stupid as it introduces failure modes
without adding any reasonable functionality.

Or are you stating that you have an application where the modulus is a number
computed at run time?

With that fairly unreasonable requirement go for the second solution, but then
perhaps fix the modulus checking (it's currently needlessly restricted).


Cheers & hth.,

- Alf

 

[Alf P. Steinbach]

* Ralf Goertz:

Hi,

what would be the best design for a class that represents the ring of
integers modulo some other integer? The problem is it only makes senes
to add, substract etc two such numbers if the belong to the same ring,
i.e. they have the same modulus. First, I thought of something like

typedef unsigned long long Int;

template <Int m> class Zm {
Int v; //value mod m
Zm<m>
Zm<m> & operator+=(Zm<m> r) {
v=(v+r.v)%m;
return *this;
}
...
public:
Zm<m>(const Int _v=Int(0)):v(_v%m) {}
};

With this approach, elements from different rings cannot be used
together in arithmetical operations. But of course, all possible moduli
would need to be known at compile and for each modulus there would be a
separate class.

The other approach would be

class Zm {
Int m,v;
bool valid;
Zm & operator+=(Zm r) {
valid &= (r.valid && (m==r.m));
v=(v+r.v)%m;
return *this;
}
...
public:
Zm(const Int _m, const Int _v):m(_m),v(_v%m),valid(true) {}
};

But this is not very elegant. Is there some better approach? Maybe with
derived classes?

Second approach is in general plain stupid as it introduces failure modes
without adding any reasonable functionality.

Or are you stating that you have an application where the modulus is a number
computed at run time?

With that fairly unreasonable requirement go for the second solution, but then
perhaps fix the modulus checking (it's currently needlessly restricted).


Cheers & hth.,

- Alf

 

[Stefan Ram]

valid &= (r.valid && (m==r.m));

I think one wants short-cut evaluation here, so I'd write:

valid = valid && ..

or

if( valid &&( valid = r.valid && m == r.m ))v =( v + r.v )% m;

~~

»%« does not have to be the mathematical modulo operation.
IIRC, it might differ for negative numbers.

 

[Lionel B]

Hi,

what would be the best design for a class that represents the ring of
integers modulo some other integer? The problem is it only makes senes
to add, substract etc two such numbers if the belong to the same ring,
i.e. they have the same modulus. First, I thought of something like

typedef unsigned long long Int;

template <Int m> class Zm {
Int v; //value mod m
Zm<m>
Zm<m> & operator+=(Zm<m> r) {
v=(v+r.v)%m;
return *this;
}
...
public:
Zm<m>(const Int _v=Int(0)):v(_v%m) {}
};

(lots of syntax errors there, but got the idea)

With this approach, elements from different rings cannot be used
together in arithmetical operations. But of course, all possible moduli
would need to be known at compile

Yes, to instantiate such an object the modulus would need to be a compile
time constant. Is that necessarily a problem? Are you likely to want to
vary the modulus at run time?

and for each modulus there would be a separate class.

How is that a problem?

The other approach would be

class Zm {
Int m,v;
bool valid;
Zm & operator+=(Zm r) {
valid &= (r.valid && (m==r.m));
v=(v+r.v)%m;
return *this;
}
...
public:
Zm(const Int _m, const Int _v):m(_m),v(_v%m),valid(true) {}
};

But this is not very elegant. Is there some better approach? Maybe with
derived classes?

BTW, I'd probably make the modulus m const here... can't think why you
might want it not to be. Also your validity checking looks suspect.

If you're going to allow the possibility of "invalid" operations, you
have to think about what you want to happen if an invalid operation is
attempted. Eg. is that to be considered a programmer error, or a "user
input error", or ... what?

If the former, I'd simply use 'assert(m == r.m)' and so on for debugging
purposes.

If the latter, things get hairier, as you then need to think how to
recover from an invalid attempt. You might then consider using exceptions.

 

[Marcel Müller]

Hi,

template <Int m> class Zm [...]
With this approach, elements from different rings cannot be used
together in arithmetical operations.

No, you can provide overloads for the global binary operators.

But since there is no general semantic for arithmetic operations of
modulo types with different domains, it makes only limited sense.

Should 5<7> + 3<4> be 1<7> or 0<4> or simply 8?


Marcel

 

[Ralf Goertz]

I think one wants short-cut evaluation here, so I'd write:

valid = valid && ..

Ok

»%« does not have to be the mathematical modulo operation. IIRC, it
might differ for negative numbers.

But my type Int is unsigned so there should be no problem.

Ralf

 

[Erik Wikström]

Hi,

template <Int m> class Zm [...]
With this approach, elements from different rings cannot be used
together in arithmetical operations.

No, you can provide overloads for the global binary operators.

But since there is no general semantic for arithmetic operations of
modulo types with different domains, it makes only limited sense.

Should 5<7> + 3<4> be 1<7> or 0<4> or simply 8?

It might throw an exception.

 

[Ralf Goertz]

(lots of syntax errors there, but got the idea)

Really? I see only one, the lonely "Zm<m>", I don't know how it got
there. I copied those line from a working example, which compiled fine
with g++ 4.2.

Yes, to instantiate such an object the modulus would need to be a
compile time constant. Is that necessarily a problem? Are you likely to
want to vary the modulus at run time?

It is not a problem yet. So far, I use only a few moduli. But then this
approach is a dead end if I want to generalize it to varying moduli.

How is that a problem?

Don't know. If there where thousands of moduli there would be very many
operator overloads. Doesn't that make the executable very big?

BTW, I'd probably make the modulus m const here... can't think why you
might want it not to be.
Ok.

Also your validity checking looks suspect.

If you're going to allow the possibility of "invalid" operations, you
have to think about what you want to happen if an invalid operation is
attempted. Eg. is that to be considered a programmer error, or a "user
input error", or ... what?

A user input error. Like in an interpreted language.

If the former, I'd simply use 'assert(m == r.m)' and so on for
debugging purposes.

If the latter, things get hairier, as you then need to think how to
recover from an invalid attempt. You might then consider using
exceptions.

The result of the user input will be the output of the computation. If
it is invalid, I Just say so.

 

[James Kanze]

template <Int m> class Zm [...]
With this approach, elements from different rings cannot be used
together in arithmetical operations.

No, you can provide overloads for the global binary operators.
But since there is no general semantic for arithmetic
operations of modulo types with different domains, it makes
only limited sense.
Should 5<7> + 3<4> be 1<7> or 0<4> or simply 8?

[/QUOTE]

It might throw an exception.

Or result in an assertion failure. (Or in this case, where the
moduli are known at compile time, not compile.)

In answer to the original posting: I'd design a class in which
the modulus was an argument to the constructor, with an
assertion that the two moduli were the same in each binary
operator. I'd probably derive a class template from that, in
which the modulus was a template argument; this would provide
compile time type checking when the moduli are known at compile
time. (It would also answer the concern of code bloat if there
were thousands of different moduli, since all of its overloaded
operators would be simple inline functions which forward to the
base class.)

 

[Lionel B]

[...]

A user input error. Like in an interpreted language.


The result of the user input will be the output of the computation. If
it is invalid, I Just say so.

Ok, I'd definitely go with exceptions then; that way it will be far easier
to handle cases where a modulus mismatch is detected within nested
constructs, particularly function (including operator) calls. The
alternative would be an ugly and error-prone handling of error conditions
throughout your code.

See also James Kanze's reply regarding an implementation.

 

[Ralf Goertz]

In answer to the original posting: I'd design a class in which the
modulus was an argument to the constructor, with an assertion that the
two moduli were the same in each binary operator. I'd probably derive
a class template from that, in which the modulus was a template
argument; this would provide compile time type checking when the
moduli are known at compile time. (It would also answer the concern
of code bloat if there were thousands of different moduli, since all
of its overloaded operators would be simple inline functions which
forward to the base class.)

Okay, thanks, that seems to be the way to go. Thanks for all replies.

 

[Kai-Uwe Bux]

what would be the best design for a class that represents the ring of
integers modulo some other integer? The problem is it only makes senes
to add, substract etc two such numbers if the belong to the same ring,
i.e. they have the same modulus.

[snip]

This is absolutely true for general rings. However, in the special case of
Z_m, note that you could define binary operations as follows:

+,-,x : Z_m x Z_n ---> Z_gcd(m,n)

In the case that m = n, the gcd does not change and you get the obvious map.
If m and n differ, you still get a result, but the modulus shrinks. This
way, the result is defined in the largest quotient of Z where it makes
sense.

Note: I do not advocate the above as the right way to go. In the particular
application you have in mind, it might be better to flag operations with
mixed arguments (either by assert() or by throwing an exception). Thus, the
method described just adds to your list of options.


Best

Kai-Uwe Bux

 

[Ralf Goertz]

what would be the best design for a class that represents the ring of
integers modulo some other integer? The problem is it only makes senes
to add, substract etc two such numbers if the belong to the same ring,
i.e. they have the same modulus.

[snip]

This is absolutely true for general rings. However, in the special case
of Z_m, note that you could define binary operations as follows:

+,-,x : Z_m x Z_n ---> Z_gcd(m,n)

In the case that m = n, the gcd does not change and you get the obvious
map. If m and n differ, you still get a result, but the modulus
shrinks. This way, the result is defined in the largest quotient of Z
where it makes sense.

Well, that's an interesting idea even though I don't have any real use
for it now. In most cases my moduli are primes so with mixed moduli I
would end up in Z.

Note: I do not advocate the above as the right way to go. In the
particular application you have in mind, it might be better to flag
operations with mixed arguments (either by assert() or by throwing an
exception). Thus, the method described just adds to your list of
options.

Thanks,

Ralf