<div dir="ltr">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).<div>
<br></div><div style>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...</div>
<div style><br></div><div style>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.</div>
<div style><br></div><div style>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 (!)).</div>
<div style><br></div><div style>I don't really know how well it optimizes, but Integer is actually (if you're using GMP with your ghc):</div><div style><br></div><div style><div>data Integer = S# Int# | J# Int# ByteArray# -- small integers and large integers, respectively</div>
<div><br></div><div style>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.</div><div style><br></div>
<div style>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.</div>
<div style><br></div><div style>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]).</div>
</div><div style><br></div><div style>[1] <a href="http://homepage.cs.uiowa.edu/~jones/bcd/divide.html">http://homepage.cs.uiowa.edu/~jones/bcd/divide.html</a></div><div style>[2] <a href="http://hackage.haskell.org/package/safeint">http://hackage.haskell.org/package/safeint</a></div>
<div style><br></div><div style>Kyle</div><div style><br></div><div style>* 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.</div>
</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Mon, Aug 19, 2013 at 9:07 PM, Richard A. O'Keefe <span dir="ltr"><<a href="mailto:ok@cs.otago.ac.nz" target="_blank">ok@cs.otago.ac.nz</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im"><br>
On 20/08/2013, at 3:43 AM, Kyle Miller wrote:<br>
<br>
> On Sun, Aug 18, 2013 at 8:04 PM, Richard A. O'Keefe <<a href="mailto:ok@cs.otago.ac.nz">ok@cs.otago.ac.nz</a>> wrote:<br>
> The argument for twos-complement, which always puzzled me, is that the other<br>
> systems have two ways to represent zero. I never found this to be a problem,<br>
> not even for bitwise operations, on the B6700. I *did* find "abs x < 0"<br>
> succeeding to be a pain in the posterior. (The B6700 had two different tests:<br>
> 'are these two numbers equal' and 'are these two bit patterns equal'.)<br>
><br>
> 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.<br>
<br>
</div>To me, that's not a better argument. It isn't even a _good_ argument.<br>
It amounts to saying "if you do things wrong, you can justify it by<br>
saying you're really doing something else right, and it's the programmer's<br>
fault for wanting the wrong thing."<br>
<br>
One great thing about the B6700 was that you were guaranteed<br>
EITHER the mathematically correct answer in the numbers you were<br>
thinking in terms of OR an exception telling you the machine couldn't<br>
do what you wanted. When it comes to *applications* programming,<br>
the number of times I have *wanted* arithmetic modulo 2^n (in the last<br>
40 years) can be counted on the fingers of one ear.<br>
<br>
You may call it "multiplication work[ing] as expected" when the product of two<br>
positive numbers comes out negative; I call it a wrong answer.<br>
<br>
Prelude> let tens = 1 : map (*10) tens :: [Int]<br>
Prelude> take 19 tens<br>
[1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000]<br>
Prelude> [x * x | x <- take 19 tens]<br>
[1,100,10000,1000000,100000000,10000000000,1000000000000,100000000000000,10000000000000000,1000000000000000000,7766279631452241920,1864712049423024128,2003764205206896640,-2537764290115403776,4477988020393345024,5076944270305263616,-8814407033341083648,4003012203950112768,-5527149226598858752]<br>
<br>
Yes, I know that Haskell has Integer.<br>
If I want to do more arithmetic than a bit of simple counting,<br>
I like to use it.<br>
The gibberish that Int multiplication spewed out above is why.<br>
<br>
Roughly speaking, there are three ways to handle integer<br>
arithmetic: the Lisp way, the Ada way, and the Java way.<br>
Lisp just gets it right (think Haskell's "Integer" type).<br>
Java *defines* wrong answers to be "right".<br>
Ada recognises that sometimes you want modular arithmetic (so it offers you<br>
modular types) and sometimes you don't (so it offers you bounded but<br>
non-modular types, where overflow is trapped).<br>
<br>
Even the C standard is careful to allow signed arithmetic to trap overflows.<br>
<br>
When we tell our students that there is an integer N > 0 such that N+1 < 0,<br>
first they are shocked and confused, then they forget about it, and then<br>
they are caught by it, and at last they remember it, but aren't sure what<br>
they can _do_ about it in Java.<br>
<br>
</blockquote></div><br></div>