Re: types, was New Book: The School of Niklaus Wirth

| > [...] and signed arithmetic is *not* modulo-2^k arithmetic.
|
| Well, it is, in a sense (you have an offset of 2^(k-1), but that's not
| a very strong difference).


For addition and subtraction, the actual operation as a function
taking a pair of bit-patterns to a new bit-pattern is identical,
whether you interpret the bit patterns as unsigned or signed 2's
complement. (This is not true for 1's complement, of course.) So,
yes, you can think of 2's complement signed arithmetic as arithmetic
mod 2^n, with an unusual set of choices of representatives of the
equivalence classes.


For *division*, however, things break down: 1/-1 is -1 in signed
arithmetic, but 0 in unsigned arithmetic. The unsigned form gives you
the division in the ring of integers mod 2^n, but the signed form does
not.


I don't remember off-hand how multiplication works out, and don't feel
like thinking about it right now. (I don't think it's the same,
though.)


> You may be confusing this with C, where signed arithmetic overflow
> has undefined behaviour (probably because modulo arithmetic for
> signed integers was considered too unimportant and too variant to be
> a useful part of the standard).


Actually, this has to do with what hardware can implement cheaply.
Many machines can, if you ask, trap signed arithmetic overflow; I
think there may have been some that *always* trap it, whether you want
them to or not. The non-trapping behavior of unsigned arithmetic is
in C exactly to give you a guaranteed way to do mod 2^n arithmetic -
and in practice I don't think anyone's come up with a machine that
implements unsigned arithmetic and cannot be told to ignore overflows
in it. (There have been machines that didn't really implement
unsigned arithmetic at all. On those, it can be pretty expensive....)


-- Jerry

Return to the comp.compilers page.
Search the comp.compilers archives again.