Re: [boost] Infinite precision integer draft

From: Carlo Wood (carlo_at_[hidden])
Date: 2006-05-29 11:15:59

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_at_[hidden]>