Are computer integers a finite group (under addition with overflow)?

Question

The integers and the integers modulo a prime are both groups under addition.

What about the computer representation of integers (e.g. int64)?

It's closed under addition, since a sum that is too large wraps around to the negatives. It also inherits the other group properties from the integers (associativity, identity, inverse).

So int64 seems like a finite group, but am I missing anything?

Answer 1

If you just let overflows happen without doing anything about it, and in particular with 2's complement representation (or unsigned), a computer's $n$-bit integer representation becomes the integers modulo $2^n$. So yes, you're entirely right: It is a finite group (and with multiplication becomes a finite ring).

(As a side note, working with and thinking about 2's complement became a lot easier for me once I realized this. No one really told me during my education, so for ages I was stuck having to remember all the details in the algorithm for taking negatives, i.e. actually taking the 2's complement. Now that I have the algebraic knowledge of what's actually going on, I can just deduce the algorithm on the fly whenever I need it.)

It's not entirely obvious to check explicitly that they satisfy, say, associativity when overflow is in the picture. It's easier to set up the obvious bijection with the integers modulo $2^n$ and show that addition stays the same, and prove the group properties that way.

Answer 2

You've checked all the axioms, so you're fine. The $n$-bit integers, whether they start at $0$ or $-2^{n-1}$, are isomorphic to the order-$2^n$ cyclic group.

Answer 3

One point to avoid tripping on:

#include <stdio.h>
#include <limits.h>

int main() {
  int x = INT_MIN;
  int y = -x;
  printf("%d, %d\n", x, y);
  printf("%d\n", x+y);
}

prints on my machine

-2147483648, -2147483648
0

In twos complement, there is one more negative number than there are positives. So you might worry that nothing happens when you try to negate INT_MIN. But, it all works out correctly! For the $k$-bit signed integers to be isomorphic to $\mathbb{Z} / 2^k$ you must line them up correctly, e.g. for $k=3$:

0  1  2  3  4  5  6  7
0  1  2  3 -4 -3 -2 -1

For example the element "6" of $\mathbb{Z} / 2^k$ is represented by -2 and "4" by -4. In particular it's true that -(-4) = -4, because in this group, 4 is its own additive inverse. So the program above is correct (note: correct according to $\mathbb{Z}/2^k$, not $\mathbb{Z}$), because $-x = x$ and $x + x = 0$ mod $2^k$.

In general INT_MIN corresponds to $2^{k-1}$ and is its own additive inverse:

0  1 ... 2^(k-1)-1  2^(k-1) ...  2^k - 1
0  1 ... INT_MAX    INT_MIN ...     -1

Answer 4

The C Standard allows, but does not require, that implementations targeting two's-complement platforms extend the language to process signed arithmetic in quiet wraparound function. According to the published Rationale, the authors of the Standard expected that commonplace implementations would only process signed and unsigned arithmetic differently when processing operations not associated with the abstract algebraic group/ring (e.g. division, relational operators, etc.). Since unsigned arithmetic behaves as an algebraic ring, that would suggest that they expected that signed arithmetic do so as well, at least with regard to the ring operators. Modern compilers, however, cannot be relied upon to generate code that behaves meaningfully when an overflow occurs when full optimizations are enabled. Versions of the gcc compiler targeting typical 32-bit platforms, for example, if given a function like:

unsigned mul_mod_65536(unsigned short x, unsigned short y)
{ return (x*y) & 0xFFFFu; }

will sometimes use the fact that they're not required to behave meaningfully if x is above 2147483647/y to infer that functions will never receive input that would cause x to exceed that value. Compilers used to process signed arithmetic as an algebraic ring, but on "modern" compilers signed integer arithmetic isn't closed under addition nor multiplication, and is thus not a group much less a ring.