[Haskell-cafe] abs minBound < (0 :: Int) && negate minBound == (minBound :: Int)

[Kyle Miller]

By "working as expected" I actually just meant that they distribute (as in
a(b+c)=ab+ac) and commute (ab=ba and a+b=b+a), and those are true in all
cases with two's compliment using simple adder and multiplier hardware*.
 The interpretation of any of these numbers being positive or negative is
specious, but people still do it because it works reasonably well for small
integers.  Also, there's the definite advantage that you can use the same
instructions for adding/multiplying signed and unsigned integers (for
instance, pointer arithmetic).

You mention that the B6700 trapped on overflows.  While this is a nice
feature, this has nothing to do with the number format.  The Intel hardware
could have come with overflow trapping, yet it didn't...

One example of a nice thing about doing computations modulo 2^n is that you
can do a bit twiddling trick called reciprocal multiplication (maybe
sometimes called magic number multiplication).  One reference for this is
at [1].  Another reference is Hacker's Delight.  But maybe you can save
this for your ear's fingers.

I can't really say I understand why anyone would actually want to use Int
(unless they knew they wanted a modulo 2^n Int).  I think it's a bit of a
shame it was given such a simple name instead of something like FastInt or
some such (and in any case it's probably safer to use Int32 or Int64 since
Int only guarantees representing signed numbers up to about 2^29 (!)).

I don't really know how well it optimizes, but Integer is actually (if
you're using GMP with your ghc):

data Integer = S# Int# | J# Int# ByteArray#  -- small integers and large
integers, respectively

That Int# is the same as in "data Int = I# Int#", so you're not really
saving anything, other than skipping bounds checking, by using Int instead
of Integer.

Where are you getting that about C?  Do you mean that it's careful to allow
implementations to decide to trap overflows?  Because as far as I can tell,
the C standard just says signed overflows give undefined behavior.

Exercise for the reader: Make a new integer type called SafeInt... scratch
that. The name was too good not to be taken, and sure enough, there's [2].
 Although I was going to propose defining "data SafeInt = Overflow | SI
Int64" and making an instance Num SafeInt which propagates Overflow (rather
than using exceptions like in [2]).

[1] http://homepage.cs.uiowa.edu/~jones/bcd/divide.html
[2] http://hackage.haskell.org/package/safeint

Kyle

* It's unclear to me how important simple adder and multiplier hardware is
these days. But, at least two's complement doesn't require defining
case-by-case behavior as I'd expect a sign-and-magnitude operations to be
defined.


On Mon, Aug 19, 2013 at 9:07 PM, Richard A. O'Keefe <ok at cs.otago.ac.nz>wrote:

>
> On 20/08/2013, at 3:43 AM, Kyle Miller wrote:
>
> > On Sun, Aug 18, 2013 at 8:04 PM, Richard A. O'Keefe <ok at cs.otago.ac.nz>
> wrote:
> > The argument for twos-complement, which always puzzled me, is that the
> other
> > systems have two ways to represent zero.  I never found this to be a
> problem,
> > not even for bitwise operations, on the B6700.  I *did* find "abs x < 0"
> > succeeding to be a pain in the posterior.  (The B6700 had two different
> tests:
> > 'are these two numbers equal' and 'are these two bit patterns equal'.)
> >
> > I think a better argument for twos complement is that you're just doing
> all of your computations modulo 2^n (where n is 32 or 64 or whatever), and
> addition and multiplication work as expected modulo anything.
>
> To me, that's not a better argument.  It isn't even a _good_ argument.
> It amounts to saying "if you do things wrong, you can justify it by
> saying you're really doing something else right, and it's the programmer's
> fault for wanting the wrong thing."
>
> One great thing about the B6700 was that you were guaranteed
> EITHER the mathematically correct answer in the numbers you were
> thinking in terms of OR an exception telling you the machine couldn't
> do what you wanted.  When it comes to *applications* programming,
> the number of times I have *wanted* arithmetic modulo 2^n (in the last
> 40 years) can be counted on the fingers of one ear.
>
> You may call it "multiplication work[ing] as expected" when the product of
> two
> positive numbers comes out negative; I call it a wrong answer.
>
> Prelude> let tens = 1 : map (*10) tens :: [Int]
> Prelude> take 19 tens
>
> [1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000]
> Prelude> [x * x | x <- take 19 tens]
>
> [1,100,10000,1000000,100000000,10000000000,1000000000000,100000000000000,10000000000000000,1000000000000000000,7766279631452241920,1864712049423024128,2003764205206896640,-2537764290115403776,4477988020393345024,5076944270305263616,-8814407033341083648,4003012203950112768,-5527149226598858752]
>
> Yes, I know that Haskell has Integer.
> If I want to do more arithmetic than a bit of simple counting,
> I like to use it.
> The gibberish that Int multiplication spewed out above is why.
>
> Roughly speaking, there are three ways to handle integer
> arithmetic: the Lisp way, the Ada way, and the Java way.
> Lisp just gets it right (think Haskell's "Integer" type).
> Java *defines* wrong answers to be "right".
> Ada recognises that sometimes you want modular arithmetic (so it offers you
> modular types) and sometimes you don't (so it offers you bounded but
> non-modular types, where overflow is trapped).
>
> Even the C standard is careful to allow signed arithmetic to trap
> overflows.
>
> When we tell our students that there is an integer N > 0 such that N+1 < 0,
> first they are shocked and confused, then they forget about it, and then
> they are caught by it, and at last they remember it, but aren't sure what
> they can _do_ about it in Java.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130820/f97eccdd/attachment.htm>