Xref: utzoo comp.theory:390 comp.misc:8327 comp.lang.misc:4267
Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!hp4nl!charon!piring.cwi.nl!lambert
From: lambert@piring.cwi.nl (Lambert Meertens)
Newsgroups: comp.theory,comp.misc,comp.lang.misc
Subject: Re: What if the Divisor is Negative?  (was Re: Modulus)
Message-ID: <8841@boring.cwi.nl>
Date: 26 Feb 90 19:14:24 GMT
References: <4356@daffy.cs.wisc.edu>
Sender: news@cwi.nl (The Daily Dross)
Reply-To: lambert@cwi.nl (Lambert Meertens)
Followup-To: comp.theory
Organization: CWI, Amsterdam
Lines: 50
Sender:

In article <4356@daffy.cs.wisc.edu> lori@rt7.cs.wisc.edu (Lori Lehman) writes:
) 
) What happens when the
) divisor is _negative_?  That is, how do we define the following?
) 
)     (e)   5 div -3,
)     (f)   5 mod -3,
) 
) ONE POSSIBLE SOLUTION
) ---------------------
) 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.
) In (e) and (f), we get
) 
)     q = -1,  r = 2,           5 = -1(-3) + 2,

It seems to me that this does not satisfy 0 <= r < -3.  In fact, an
exhaustive search of that range gave no solutions :-)

) 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?

In the programming language ABC, x mod y is defined for all x and y, y <> 0,
(also non-integers) by two requirements.
The first is the obvious requirement that x mod y differs from x by an
integral multiple of y.  The second is that

    0 <= (x mod y)/y < 1.

Thus (-5) mod 3 = 1, and 5 mod -3 = -1.

Having designed this myself I should not dare to say that this is the most
logical definition, but I find it both aesthetically pleasing and easy to
reason with.  For example, it follows from these properties that, for
integral n, (x+n*y) mod y = x mod y.

The problem with div and rem was solved in ABC by not having any; you have
to spell out what you want (e.g. floor(x/y)).

-- 

--Lambert Meertens, CWI, Amsterdam; lambert@cwi.nl