1
$\begingroup$

In standard computer arithmetic, there are two sets of numbers.

  • N-bit unsigned numbers. The elements are natural numbers in $(0, 2^N]$. Arithmetic operations is defined as for the natural numbers except all operations are modulo $2^N$.

  • N-bit signed numbers. The elements are integers in $(-2^{N-1}, 2^{N-1}]$. Arithmetic operations rules for complement [1] [2] arithmetic are more complex than a simple modulo.

    • For example, $-2^{N-1} = --2^{N-1} = 2^{N-1}-1 + 1$.

What are these two sets (and their elements) called?

I understand these sets of numbers and their corresponding operational semantics completely, but I want to know how these sets and their elements are correctly named from a mathematical perspective. For example: the generic concept "unsigned numbers" and their arithmetic operations is more correctly (or usually) called something like "the field of natural numbers".

  • 3
    Aren't unsigned numbers the the integers (avoiding the question of whether $0$ is a natural) in $[0,2^N)$? I thought $0$ was allowed and the largest was $2^N-1$. Similarly for signed, though it depends on whether you use sign-magnitude, two's complement or one's complement. In two's complement you can express $-2^{N-1}$, but not $2^{N-1}$. You seem interested in these details.2011-06-19

1 Answers 1

3

As far as I can tell from your description (I don't know much about CS), these structures are both $\mathbb{Z}/2^N\mathbb{Z}$, i.e. the integers modulo $2^N$, only using different sets of representatives. The elements of this structure could be referred to as simply "integers modulo $2^N$", or perhaps "equivalance classes of $\mathbb{Z}$ modulo $2^N$".

When we talk about the integers mod $n$, we usually use the symbols $0,1,\ldots,n-1$ to refer to the elements of $\mathbb{Z}/n\mathbb{Z}$, but the elements are, properly, equivalence classes of $\sim$ where $a\sim b$ when $n$ divides $a-b$. There's no mathematical reason for using the representatives $\{0,1,\ldots,n-1\}$; we could just as easily use $\{1,2,\ldots,n\}$, or $\{-n+1,-n+2,\ldots,0\}$, or $\{5n,1,2,\ldots,n-1\}$, etc. and different choices don't change the structure. This seems to be where they explain it in the article.

By the way, $\mathbb{Z}/2^N\mathbb{Z}$ is not finite field if $N\neq 1$, and the natural numbers do not form a field. The proper name for the structures $\mathbb{Z}/n\mathbb{Z}$ is a ring (this ring is a field if and only if $n$ is a prime number), and the natural numbers $\mathbb{N}$ form a semigroup. The integers $\mathbb{Z}$ are a ring, however.

  • 1
    Yes and no. Depending on flags set for overflow and underflow they may not be a ring. And there is additional structure which varies between them - in particular, there is an almost-total "division" function which is usually $x/y = \lfloor \frac{x}{y} \rfloor$ or sometimes $x/y = \mathop{\mathrm{sgn}}(\frac{x}{y}) \lfloor | \frac{x}{y} | \rfloor$ and this then depends on the particular representative values.2011-06-19