fixed size integer arithmetic

[Hans Aberg]

On 30 Aug 2007, at 03:39, Martin d Anjou wrote:

> No, N is not a power of 2. It is fixed though.
>
>>> It should, of course, be "arithmetic in Z_N".  I don't know why a
>>> spurious "Z/" crept in.  I do know that I need to improve my proof
>>> reading.
>>
>> The modern construction is Z_n := Z/nZ, the ring of integers Z
>> divided out with the ideal nZ = (n) = {kn| k in Z}. One can also
>> construct Z_n as Z divided out with the equivalence relation mod n.
>
> I understand the ring of integers.
>
>> As for the original question, n = 2^k, where k is the number of bits.
>> If one uses 2s complement representation for signed integral types,
>> the only difference between signed and unsigned integral types is the
>> lifting of the coset representatives of Z_n into Z. So they can be
>> replaced by a single type with different (signed/unsigned) printing
>> functions.
>
> I don't understand the "coset representatives of Z_n into Z".

If R is a (commutative) ring, and I an ideal of R, I call "cosets"  
the sets of the form r + I = {r + x| x in I}, where r in R. Then a ~  
b <=> a - b in I is an equivalence relation: a, b are equivalent  
exactly when they are in the same coset; one can define R/~, which  
can also be given a ring structure, written R/I.

In Z, the ideals are just the sets of the form (n) = nZ := {kn| k in  
Z}. Fix an n; then the cosets, the members of the ring Z/nZ, are of  
the form k + nZ, also written k with a stroke over: the image of k  
under the map pi_n: Z -> Z/nZ. The point here is that the  
construction does not single out any specific integers (see below).  
The equivalence relation a ~ b above is though the same as a = b mod  
n, and each coset k + nZ consists of the set of integers that give  
the same remainder k when divided by n.

Now, when choosing "unsigned integers", just take coset  
representatives 0 + nZ, ..., (n-1) + nZ, and for "(2s complement)  
signed integers", when n is even -n/2 + nZ, ..., (n/2 - 1) + nZ, and  
when n is uneven -(n-1)/2 + nZ, ..., (n-1)/2 + nZ. These can be  
described as sections, that is functions s: nZ -> Z satisfying pi o s  
= 1 (identity).

But the arithmetic actually takes place in the ring Z_n := Z/nZ. So  
in principle, one can have just one data type, with different  
sections at need. This does not work with 1s complement signed  
integers, but it seems that data type has fallen out of vogue.

   Hans Aberg