brian@digi-g.UUCP (Brian Westley) (08/28/84)
<Arthur bruised his upper arm> Should ((-2) % 3) equal -2 or 1? Our machine returns -2, but the posted corewars game seems to assume a%b always returns 0..b-1; is modulus for negative lefthand args well defined? What about Pascal mod function? Modula Modulus? Accepted mathematical definition of modulus? Merlyn % Leroy
qwerty@drutx.UUCP (JonesBD) (08/29/84)
K&R states the following re: % operator: 1) operator yields remainder of division of first exp. by second exp. There are further statements under division about remainders: 2) It is always true for b != 0 that (a/b)*b + a%b = a 3) "On all machines covered by this manual, the remainder has the same sign as the dividend." 4) When positive integers are divided, truncation is toward zero, but the form of truncation is machine-dependent if either operand is negative. From the above, in particular 3), it seems that a%b with 'a' negative should return a negative number. However, the also seems to be considerable phrasing present to indicate that machine dependencies may cause problems with code portability. Its so nice to use a tight, well defined language :-).
henry@utzoo.UUCP (Henry Spencer) (09/09/84)
The basic problem here is simple: there is no unique way to turn a
non-integer result of integer division into a <quotient, remainder>
pair, where both quotient and remainder are integers. There are at
least four different ways to do this (truncate quotient towards zero,
truncate toward minus infinity, truncate to give positive remainder,
rounding with some sort of tie-breaking rule). Several of these give
the same answer when all numbers are positive, but negative numbers
expose the differences.
Fortran picked, more or less arbitrarily, truncate-towards-zero, and
many machines have followed its lead, but that's by no means universal.
Note that two's-complement arithmetic shifts implement truncate-towards-
minus-infinity division, not truncate-towards-zero.
The current draft of the ANSI C standard explicitly states that either
truncate-towards-zero or truncate-towards-minus-infinity is legitimate,
and the choice is implementation-dependent.
The only safe rule is to avoid integer division with negative operands,
unless you don't care about the rounding behavior. Portable programs
should not depend on the rounding behavior of integer division.
--
Henry Spencer @ U of Toronto Zoology
{allegra,ihnp4,linus,decvax}!utzoo!henrychris@umcp-cs.UUCP (Chris Torek) (09/10/84)
But that one fails for the "most negative" number on some machines!
You have to take care of negatives whose negation is still negative
or some similar rot.
--
In-Real-Life: Chris Torek, Univ of MD Comp Sci (301) 454-7690
UUCP: {seismo,allegra,brl-bmd}!umcp-cs!chris
CSNet: chris@umcp-cs ARPA: chris@marylandjrv@mitre-bedford.ARPA (09/10/84)
>Should ((-2) % 3) equal -2 or 1? Our machine returns -2, but the posted >corewars game seems to assume a%b always returns 0..b-1; is modulus for >negative lefthand args well defined? What about Pascal mod function? >Modula Modulus? Accepted mathematical definition of modulus? > Merlyn % Leroy K&R apparently allow for either kind, but every time I've USED a modulus function, I needed one that returned a nonnegative number, whether the dividend was positive or negative. Has anyone ever needed the other kind? Has anyone ever needed a modulus with a negative divisor? - Jim Van Zandt
cosell@BBN-LABS-B.ARPA (09/10/84)
I has been my observation (over quite a few machines) that all you can hope for
is that '/' and '%' agree. That is, for any I and M, all you can count on is
that I = (I/M) * M + (I%M). This may seem obvious, but it is certainly
possible to bollix up the signs of things so that, for example, you might have
I = ... '+' I%M if M>0, but I = ... '-' I%M if M<0. In any event, the few
hardware folk I've talked to about this seem to believe that once the above
'reassembly' equation is satisfied, they don't care any more. Mostly I've
found that the compiler writers are the same way, though: '/' gets you the
'quotient' from the machines native 'integer divide' instructions, '%' gets you
the 'remainder' from that instruction. Pleas that they are just perpetuating
the mathematical unsophistication of the hardware designers fall on deaf ears.
The heart of the misunderstanding is that some folk seem to beliave that a
proper 'invariant' for the mod function should be:
((-1)*a) mod M = -1 * (a mod M).
This is INCORRECT!!! The proper invariant (as any mathematician will tell you)
is that
a mod M = (a - M) mod M = (a + M) mod M
Notice that this latter invariant is violated by most of the dumb-remainder
implementations.
I've mostly given up: I brute-force make my numbers all be postive (saving the
signs away), do '/' or '%' (which is usually predictable and correct for
all-positive operands), and then do a 'switch' to tune things depending on what
the signs used to be.
/berniegwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (09/10/84)
The "most negative number" is always a problem on 2's complement machines. Rather than have every routine have a special case for this, we usually prohibit it the same way we prohibit numbers larger than the largest. Sometimes one can handle the "most negative number" without making a special case; atoi() is an example (use a negative accumulator).
guido@mcvax.UUCP (Guido van Rossum) (09/11/84)
How about this modulus function:
mod(a, b) {
int m = a % b;
if ((m < 0) != (b < 0)) m += b;
return m;
}
This one even works for negative b.
You can also do the following:
#define mod(a, b) (a%b + b) % b
which should, of course, be written as
#define mod(a, b) (((a)%(b) + (b)) % (b))
and this also works for negative b (but watch side effects!).
--
Guido van Rossum, "Stamp Out BASIC" Committee, CWI, Amsterdam
guido @ mcvaxgino@voder.UUCP (Gino Bloch) (09/12/84)
The analogy that I like is `what time was it 74 hrs ago?' Very few people expect negative time ... -- Gene E. Bloch (...!nsc!voder!gino)