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

Jerry Leichter <jerrold.leichter@smarts.com>
30 Nov 2000 12:03:39 -0500

          From comp.compilers

Related articles
Re: Re: New Book: The School of Niklaus Wirth ollanes@pobox.com (Orlando Llanes) (2000-11-05)
Re: New Book: The School of Niklaus Wirth djg@argus.vki.bke.hu (Gabor DEAK JAHN) (2000-11-11)
Re: New Book: The School of Niklaus Wirth gdemont@my-deja.com (2000-11-16)
Re: New Book: The School of Niklaus Wirth jerrold.leichter@smarts.com (Jerry Leichter) (2000-11-17)
Re: New Book: The School of Niklaus Wirth fjh@cs.mu.OZ.AU (2000-11-19)
Re: New Book: The School of Niklaus Wirth jerrold.leichter@smarts.com (Jerry Leichter) (2000-11-21)
Re: types, was New Book: The School of Niklaus Wirth joachim_d@gmx.de (Joachim Durchholz) (2000-11-25)
Re: types, was New Book: The School of Niklaus Wirth jerrold.leichter@smarts.com (Jerry Leichter) (2000-11-30)
Re: types, was New Book: The School of Niklaus Wirth anton@mips.complang.tuwien.ac.at (2000-12-01)
Re: types, was New Book: The School of Niklaus Wirth jenglish@flightlab.com (2000-12-03)
| List of all articles for this month |

From: Jerry Leichter <jerrold.leichter@smarts.com>
Newsgroups: comp.compilers
Date: 30 Nov 2000 12:03:39 -0500
Organization: System Management ARTS
References: 00-11-046 00-11-082 00-11-120 00-11-122 00-11-133 00-11-141 00-11-152
Keywords: types
Posted-Date: 30 Nov 2000 12:03:39 EST

| > [...] 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


Post a followup to this message

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