Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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".

share|improve this question
2  
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. –  Ross Millikan Jun 19 '11 at 3:00
add comment

1 Answer 1

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.

share|improve this answer
    
Thanks for correcting my misuse of "field" and the clarification of "rings". –  wjl Jun 19 '11 at 1:20
    
I see your point about equivalence classes: the elements of the sets are isomorphic to each other. But, the "sets + operations we can do on them" differ, as well as the way we use them an interpret them. For instance, the operation "abs" is not isomorphic between the two sets. I was hoping that the "sets + the valid operations defined on them" with the commonly-understood semantics of computer arithmetic mapped to some well-known concept name in mathematics. –  wjl Jun 19 '11 at 1:29
    
It is more than the structures being isomorphic; the structures are identical (this can be a subtle point). As I understand it, the only difference is in how the computer is instructed to represent the equivalence classes internally. Here is an analogy: the algorithm we use to add integers might look different depending on whether we're using base 10 or base 2, but the integers are still the integers; only our representation of them changed. Anything we can do with integers in base 10 we can also do in base 2. –  Zev Chonoles Jun 19 '11 at 1:38
    
Also, there is no well-defined "absolute value" function on the ring $\mathbb{Z}/n\mathbb{Z}$ without first making an (arbitrary) choice of representatives. This should not be interpreted as $\mathbb{Z}/n\mathbb{Z}$ being a different structure when we choose different representatives; rather, as an indication that "absolute value" is not a useful concept to apply to $\mathbb{Z}/n\mathbb{Z}$ (well, it is, but in a much different way). –  Zev Chonoles Jun 19 '11 at 1:43
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. –  Peter Taylor Jun 19 '11 at 7:58
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.