17
$\begingroup$

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?

$\endgroup$
5
  • 3
    $\begingroup$ You don't need the modulus to be a prime for making it an additive group, since $2^{64}$ is decidedly not prime. $\endgroup$
    – obscurans
    May 26, 2020 at 8:55
  • 4
    $\begingroup$ For the record, this depends on the intrinsics of your computer (there's a reason why overflow in integer addition is undefined behaviour in the C++ spec). Then again, you'll probably never encounter anything where integer overflow is not wrap-around :) $\endgroup$
    – Hagen von Eitzen
    May 26, 2020 at 20:50
  • $\begingroup$ @obscurans: and indeed I suspect that's why computer programming instructors don't make a big song and dance about it. If they think about it at all, they'd expect that everyone who knows anything about group theory will know that there's a cyclic group of every order. Obviously it's possible for someone to overlook that fact (like kennysong did mentioning primes), or to overlook that wraparound is what's happending (like Arthur describes himself doing at first). But on the whole if you can make any use of the fact it's a cyclic group, you can spot that it is. $\endgroup$
    – Steve Jessop
    May 27, 2020 at 13:55
  • 2
    $\begingroup$ Primes come into it if you want to use that integer arithmetic modulo a prime is a field, whereas arithmetic module a non-prime like uint64_t is only a ring: not all elements have a multiplicative inverse. $\endgroup$
    – Steve Jessop
    May 27, 2020 at 13:57
  • 3
    $\begingroup$ @HagenvonEitzen: see supercat's answer. With optimisation, there are common C++ implementations where arithmetic is not wraparound. The underlying processor instructions are, sure, but when it reasons about valid optimisations the compiler can (and sometimes does) use equivalences that don't hold if overflow actually occurs. It's upsetting when you fall for it. Specifically, for example, the compiler might remove attempted checks for overflow gcc.gnu.org/bugzilla/show_bug.cgi?id=30475 on the principle that code which only executes after UB has already occurred, is dead code $\endgroup$
    – Steve Jessop
    May 27, 2020 at 14:24

4 Answers 4

Reset to default
27
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ Thanks for the confirmation! Though I wonder why no one talks about this (fun) fact, I couldn't find anything from googling around. $\endgroup$
    – kennysong
    May 26, 2020 at 12:38
  • 3
    $\begingroup$ @PaulSinclair: Sure, but 1's complement also forms a group, as does BCD, and literally every other encoding, because that's a property of the arithmetic, not of the encoding used. I guess I could see how it's useful as a mnemonic, though, since the defining property that makes 2's complement unique (and the hidden assumption in your proof) is that addition and subtraction work the same. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    May 27, 2020 at 0:56
  • 2
    $\begingroup$ @BlueRaja-DannyPflughoeft - I started with once you understand the representation, not "once you know only this one thing about the representation". My point (and I think, Arthur's) is that 2's complement was taught to us as just some trick that magically seemed to turn addition into subtraction. It was discovering how and why it worked that allowed us to truly understand it, and in doing so turned something that had to be memorized into something that can be easily deduced. Yes, it depends on how numbers are stored, but that is a known part of the set up we are discussing. $\endgroup$
    – Paul Sinclair
    May 27, 2020 at 1:21
  • 1
    $\begingroup$ @BlueRaja-DannyPflughoeft : 1s complement does not form a group because 1s complement does not have a unique identity element. Signed magnitude is another encoding that fails for the same reason. $\endgroup$
    – Eric Towers
    May 27, 2020 at 15:35
  • 1
    $\begingroup$ @EricTowers: Ones'-complement numbers would form a ring if the all-ones bit pattern isn't considered a number. Even viewed in that light, however, they lack the unique and useful property of two's-complement numbers that adding or multiplying the last N bits of two numbers will allow one to compute the last N bits of the result. Two's-complement is the only representation that can behave this way, because subtracting 01 from 00 must yield something that ends in 1 but not 01 (must end in 11), subtracting 001 from 000 must yield something that ends in 11 but not 011, etc. $\endgroup$
    – supercat
    May 27, 2020 at 19:32
9
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ You're doing unsigned arithmetic in the example. Why would this not be guaranteed to behave as in the algebraic ring?? $\endgroup$
    – user169852
    May 26, 2020 at 23:41
  • 3
    $\begingroup$ @Bungo: Integer promotion rules specify that on a platform where unsigned short is 16 bits and int is 32 bits, the arithmetic will be performed on a signed 32-bit int. $\endgroup$
    – supercat
    May 27, 2020 at 2:35
2
$\begingroup$

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
$\endgroup$
1
  • 5
    $\begingroup$ Which is consistent with the group theoretic fact that any group of even order must contain at least two elements that are their own inverses. (Proof: pair each element with its inverse, which may be itself. Since the identity is its own inverse and there are an even number of elements, there must be at least one other element paired with itself.) $\endgroup$
    – user169852
    May 26, 2020 at 21:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .