fixed size integer arithmetic
Hans Aberg
haberg at math.su.se
Thu Aug 30 11:23:23 CEST 2007
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
More information about the gmp-discuss
mailing list