Though I agree that a modulo is needed / should be provided, I don't agree that it should be possible to set it at runtime. Below, I'll try to argue that we need two types: One for the infinite group of integers, and a templated one (so basically, infinite number of types) for the finite groups. Modulos are things that work on everything, also all operations. In math. one would write: x = 7 x + 5 == x * x [module 37] and that wouldn't change the fact that x is an integer. So, it makes more sense set a modulo with a global function, and not just for one specific variable (as everyone already seems to agree upon(?)). Ie, one can say x = 7 set_modulo(37); assert( x + 5 == x * x ); And that would be true. This would be pretty well defined, except for printing the value of variables. With a modulo set to 37, the integer values 7 and 44 (and -30, etc) are in the same equivalence class (they are equivalent) and any such integer can be taken represent such a class. Internally, any of those values would do, but in the end, I guess, we want the same value to be printed for the same equivalence class. We could define that the only printed representative of such equivalence class has to be the smallest natural number (>= 0), in which case that representative would have simularities with an unsigned int (certainly when the modulo is consider to be 2^32 in that case), but this is not possible when the modulo is 0. In that case you either DON'T have a group (there doesn't exist an additive inverse) OR you need the negative numbers. [Note: a 'group' is a set of elements for which both, addition and subtraction is well defined, along with a few other axiomatic demands- like that there has to exist a zero, (a + b) + c == a + (b + c), etc]. Even in math, there has to be made a pretty big difference between finite groups and the few existing groups with an infinite number of elements (which, in our case, would be just the (signed) integers). Now note that you can't add two numbers with different modulo, that wouldn't make sense -- but you CAN multiply an element of a finite group with an integer (defined as adding it to itself that many times). Therefore, this would be legal code: integer n = 88; set_modulo(37); x = y * n; where 'n' would still be 88, and not an equivalence class of 14. This is why I think we need TWO types: one for finite groups, and one for normal integers (the infinite group).
From Maarten's proposal I understand that he wants the same. He seems to propose to use 'integer' for the infinite group, and 'unsigned_integer' for the finite group (with a static method to set the modulo). The only thing I disagree with is the name 'unsigned_integer'. I think it should be called 'abelian_group', something like that. [Abelian group is a group for which a + b == b + a].
There is nothing 'unsigned' about it: For the non-mathematicians, this was the unary minus sign means: When x + y is defined (gives another well defined element of the group), then 0 (zero) is defined as the (single) element for which x + 0 == x for every element x of the (finite) group. Also, there will be a unique solution to the equation x + y == 0 for every element x. '-x' is defined to be the equivalence class (element) for which x + (-x) == 0, thus -x == y. An equivalence class can be seen as a (infinite) set of all integers that are equivalent. Modulo 37, we would have: { ..., -74, -37, 0, 37, 74, ... } { ..., -73, -36, 1, 38, 75, ... } { ..., -72, -35, 2, 39, 76, ... } . . . { ..., -38, -1, 36, 73, 110, ... } which are all 37 possible elements. If you want you could represent those classes with an integer between 0 and 37. Then you could write: 5 + 32 == 0 In other words, -5 == 32. This should definitely work: abelian_group<37> x, y; // Making up my own type for a moment. x = 5; y = -x; // Unary minus works. assert(y == 32); where every binary operation between an element from a finite group and an integer is taken to mean a binary operation between two elements of that finite group, where the second element was represented by the integer (thus, also, y == -5, and y == 69). This even holds for multiplication: you can still implicitely convert the integer you are multiplying with to the finite type before multiplying; but be aware: in that case multiplication must be well defined within the group, in other words, it must be a ring (which is a group for which also multiplication is defined). Fortunately, integers modulo some integer ARE rings. The following should also be legal code: integer n = 80; abelian_group<37> x = 5; abelian_group<7> y = 5; assert(x * n == 30); assert(y * n == 1); but can't do: assert(x == y); // Eror: should not compile. Imho, that can only be achieved in the way I did: by using a templated type for the finite groups. If you'd use a type 'unsigned_integer' with a static method set_modulo, then you can never write the first piece of code. I suppose that in practise that wouldn't be a major problem in most cases-- but you never know. The fact that it wouldn't be possible to pass two elements of different sized groups to a function might become a large problem. On Mon, May 29, 2006 at 03:55:01PM +0200, Maarten Kronenburg wrote:
In my opinion the unsigned integer with a modulus is required, which is generalizing the base type unsigned int (which is modular) to any modulus. So the unsigned_integer would have a static method void set_modulus( const integer & ). The only problem is what an unsigned_integer is when a modulus is not providid, that is when the modulus is zero. Then I propose that as the user did not provide any modulus, only in this case negating a non-zero unsigned_integer will be an error. Also I propose that such an unsigned_integer will be provided by implementations, and be added to the specification.
-- Carlo Wood <carlo@alinoe.com>