Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site lsuc.UUCP
Path: utzoo!lsuc!msb
From: msb@lsuc.UUCP (Mark Brader)
Newsgroups: net.math,net.arch
Subject: Re: Integer division
Message-ID: <1091@lsuc.UUCP>
Date: Fri, 31-Jan-86 04:55:43 EST
Article-I.D.: lsuc.1091
Posted: Fri Jan 31 04:55:43 1986
Date-Received: Fri, 31-Jan-86 05:52:51 EST
References: <332@ism780c.UUCP>
Reply-To: msb@lsuc.UUCP (Mark Brader)
Distribution: net
Organization: Law Society of Upper Canada, Toronto
Lines: 54
Xref: lsuc net.math:1079 net.arch:734
Summary: I disagree with both sides

[Sorry about repeating 20-odd lines, but I needed the equation numbers]
Tim Smith (tim@ism780c.UUCP) writes in net.math:

> A recent discussion on net.arch raised the problem of defining integer
> division for negative numbers.  Most computers seem to say that -3/2 is
> -1, and -3%2 is -1.  Many people thought this was fine, but some of us
> think that -3/2 should be -2, and -3%2 should be 1.  Both sides agree
> that integer division on computers must be defined to satisfy
> 
> 	(1) (a/b)*b + a%b = a.
> 
> Everyone agreed that for positive a and b, a/b should round toward zero.
> The people who want -3/2 to be -1 argue that the following should hold:
> 
> 	(2) (-a)/b = -(a/b).
> 
> Those of us who want -3/2 to be -2 want the following to hold:
> 
> 	(3) a%b for positve b has a range of [0,b-1], not [-b+1,b-1], and
> 	(4) (a+b)/b = a/b + 1.
> 
> Are there any good mathematical grounds for choosing one alternative over
> the other here?  Note that I am not asking from a hardware point of view...
> 
> ... when I was a math major my major interest was number theory, where
> (3) and (4) are more useful than (2).

I'm going to answer this from a software person's point of view
(and therefore I'm cross-posting back to net.arch, which I don't read).

When I do an "integer division" operation, (2) is important to me.
I want the operation of dividing and then truncating at the decimal
point.  I hardly ever want the remainder as well as the quotient,
and *when I do*, the dividend is always *positive*.

When I do a % operation, I may be doing one of two things.  I may
want the remainder that goes with the division I just did -- in which
case, as I say, the dividend is, in my experience of cases of interest,
always positive.  Or I may want to do the mathematical operation of
taking the modulus, which is expressed by (3); and in that case, the
"dividend" may be negative or positive.

This puts me squarely in the *third* camp.  I want (2) *and* (3),
and I don't give a dam~ about (1) for negative dividends.  So I
want -3/2, or rather (-3)/2, to be -1, and (-3)%2 to be +1.

I must make one hardware-type comment: I think one argument, perhaps
unconscious, in favor of (1) is that computers (the ones I know, anyway)
compute quotient and remainder simultaneously.  To this I say, yes, but
why should they do that anyway?  Few languages have DIVIDE X BY D GIVING
Q REMAINDER R., and most often the second computed value is unused anyway.
I see no reason that this tradition should give extra weight to (1).

Mark Brader