Xref: utzoo comp.theory:379 comp.misc:8302 comp.lang.misc:4239 Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uwm.edu!psuvax1!callahan From: callahan@cs.psu.edu (Paul B. Callahan) Newsgroups: comp.theory,comp.misc,comp.lang.misc Subject: Re: What if the Divisor is Negative? (was Re: Modulus) Message-ID: Date: 24 Feb 90 01:54:02 GMT References: <4356@daffy.cs.wisc.edu> Organization: Johns Hopkins University Computer Science (posting from PSU) Lines: 56 In article <4356@daffy.cs.wisc.edu> lori@rt7.cs.wisc.edu (Lori Lehman) writes: >Mathematically speaking, given integers m and n (n <> 0), we can >solve for q and r in the equation > > m = qn + r, > >where q and r are integers. If we force 0 <= r < n, we can get a unique >solution. The only problem with this is that I don't see why we should _force_ anything. Instead of changing the definitions to fit our preconceived notions of what the answer should be, why not simply start from the simplest set of assumptions and derive the rest? We use one nasty (i.e. discontinuous and seemingly artificial) function floor, and base the rest on it. Thus, we define m div n = floor(m/n) m mod n = m - n*(m div n) "floor" is of course, well defined for all reals. In general, floor(x) is the _unique integer_ i satisfying i <= x < i+1 Now, we can see for ourselves what happens when negative values are used for n. floor(m/n) <= m/n < floor(m/n)+1 [By def.] n*floor(m/n) >= m > n*floor(m/n)+n [* some n<0] 0 >= m-n*floor(m/n) > n [- n*floor(m/n)] 0 >= m mod n > n [By def.] So this would imply that m mod some negative n gives 0,-1,-2,...,n+1. I trust this definition because it originated from only one dubious assumption, namely the use of the floor function. Your definition required the additional dubious assumption that mod must always return a nonnegative value. Though you did not actually use an absolute value, I think that if you go back to your definition you'll discover where you needed one. Another nice thing about this definition is that m and n need not be integers. In fact, if n is 2*pi and and m is some arbitrary real, then we can use this formula to force an angle into the interval [0,2*pi). >ESSAY QUESTION: Is this the way God intended "div" and "mod" to work? I'm not sure God intended us to do things as slimy as coercing real arithmetic to fit integer arithmetic and integer arithmetic to fit modular arithmetic. If we consider the cyclic group of addition mod n for some positive n, then we completely avoid the issue of how to treat negative numbers, since the only numbers that exist are 0,1,...,n-1. Paul Callahan callahan@crabcake.cs.jhu.edu callahan@psuvax1.cs.psu.edu