Xref: utzoo comp.theory:378 comp.misc:8297 comp.lang.misc:4232
Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uwm.edu!uwvax!daffy!rt7.cs.wisc.edu!lori
From: lori@rt7.cs.wisc.edu (Lori Lehman)
Newsgroups: comp.theory,comp.misc,comp.lang.misc
Subject: What if the Divisor is Negative?  (was Re: Modulus)
Message-ID: <4356@daffy.cs.wisc.edu>
Date: 23 Feb 90 23:20:59 GMT
Sender: news@daffy.cs.wisc.edu
Organization: U of Wisconsin CS Dept
Lines: 96



STATEMENT OF PROBLEM
--------------------

Everyone will agree that  

    (a)  5 div 3 = 1,
    (b)  5 mod 3 = 2,

and most people seem to agree that  

    (c)  -5 div 3 = -2,
    (d)  -5 mod 3 = 1.

Note that the divisor in these examples, 3, is positive.  What happens when the
divisor is _negative_?  That is, how do we define the following?

    (e)   5 div -3,
    (f)   5 mod -3,

    (g)  -5 div -3,
    (h)  -5 mod -3.
     


ONE POSSIBLE SOLUTION
---------------------

Generally speaking, given numbers m and n, we want to find the quotient and the
remainder when m is divided by n.  The quotient is "m div n" and the remainder
is "m mod n."  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.  When we have q and r, we say the _quotient_ q is  m div n  and the
_remainder_ r is  m mod n.  For example, in (a) and (b) above, we have

    q = 1,   r = 2,           5 = 1(3) + 2,
                              |   | |    |
	                      m   q n    r
    
and in (c) and (d) above, we have 

    q = -2,  r = 1,          -5 = -2(3) + 1.

This is just ONE WAY to define "quotient" and "remainder," e.g, "div" and "mod."
Okay, using this definition of div and mod, how do we define (e) through (h)?
In (e) and (f), we get

    q = -1,  r = 2,           5 = -1(-3) + 2,

and in (g) and (h), we get

    q = 2,   r = 1,          -5 = 2(-3) + 1.


To summarize thus far, we have the following:

    (a)  5 div 3 =  1      (e)  5 div -3 = -1 
    (b)  5 mod 3 =  2      (f)  5 mod -3 =  2

    (c) -5 div 3 = -2      (g) -5 div -3 =  2
    (d) -5 mod 3 =  1      (h) -5 mod -3 =  1


You can see that by this definition of div and mod, we have the following 
identities (I will not prove them in general):
              
     m div -n   ==   -( m div n) 
    -m div -n   ==   -(-m div n) 

     m mod -n   ==    m mod n
    -m mod -n   ==   -m mod n



                                * * * * * 
               

QUESTION:  Is this the best (i.e., most flexible, most logical, and most 
	   aesthetically pleasing, etc.) definition of "div" and "mod"?

BONUS QUESTION:  What does it mean to have a negative base?  Is "mod" really
		 the same as "remainder"?  Do the members of bases really have
		 to be nonnegative?
		 
ESSAY QUESTION:  Is this the way God intended "div" and "mod" to work?


--------------------------------------------------------------------------------
 Todd S. Lehman, UW-Madison  |  "Don't roll with the punches -- punch back!"
 toddl%garfield@cs.wisc.edu  |            --Healthy attitude during finals week 
--------------------------------------------------------------------------------