lori@rt7.cs.wisc.edu (Lori Lehman) (02/24/90)
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
--------------------------------------------------------------------------------callahan@cs.psu.edu (Paul B. Callahan) (02/24/90)
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
ok@goanna.oz.au (Richard O'keefe) (02/26/90)
In article <4356@daffy.cs.wisc.edu>, lori@rt7.cs.wisc.edu (Lori Lehman) writes:
[asking about X div Y when Y < 0]
The thing which keeps tripping people up is the assumption that
there is *one* "proper" definition of div and mod. Common Lisp
offers four:
(floor x y) => q r ;; round towards -oo
(ceiling x y) => q r ;; round towards +oo
(truncate x y) => q r ;; round towards 0
(round x y) => q r ;; round to nearest (on tie to even)
where in each case x = q*y + r and |r| < |y|
I have had occasion to use _each_ of these functions, and I've been glad
that the names said clearly which one I was using.
It would be useful to have something else, say
(quotient x y) => q r ;; undefined for x < 0 or y <= y
which could do whatever was fastest on a particular machine; the use of
this function would be a signal to the human reader that the arguments
were expected to be in a range where it didn't matter which opcode was
used (usually the case).steven@cwi.nl (Steven Pemberton) (02/26/90)
In article <Efc#2s@cs.psu.edu> callahan@cs.psu.edu (Paul B. Callahan) writes: > Thus, we define > m div n = floor(m/n) > m mod n = m - n*(m div n) [...] > 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). And you can get the fractional part of m with m mod 1 For an example of a language that adopts this approach (and gets mod right :-), see ABC, recently posted to the net. Steven Pemberton, CWI, Amsterdam; steven@cwi.nl "Let us go then you and I/while the night is laid out against the sky/like a smear of mustard on an old pork pie" Nice poem Tom. I have ideas for changes though, why not come over? - Ezra
chl@cs.man.ac.uk (Charles Lindsey) (02/27/90)
lori@rt7.cs.wisc.edu (Lori Lehman) writes: >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. I am delighted that "most" people are now agreed about the -ve dividends, but I do not like the proposed solution for -ve divisors. ANOTHER POSSIBLE SOLUTION ------------------------- I have no gut feeling for what 5 mod -3 should do, so let us fix div first. The consensus for -ve divisors implies that m div n = floor(m/n). Let us try to keep this for the new case. (e) 5 div -3 = -2 ( = -5 div 3 ) (g) -5 div -3 = 1 But we should like to preserve m = qn + r, which inevitably leads to (f) 5 mod -3 = -1 (h) -5 mod -3 = -2 Now try this for gut feeling, and we have, for all m and -ve n, n < m mod n <= 0 just as we had, for all m and +ve n, 0 <= m mod n < n The whole thing feels quite comfortable for me, and it just remains for some Group Theorist to report whether it is now a respectable algebra. To summarize: (a) 5 div 3 = 1 (e) 5 div -3 = -2 (b) 5 mod 3 = 2 (f) 5 mod -3 = -1 (c) -5 div 3 = -2 (g) -5 div -3 = 1 (d) -5 mod 3 = 1 (h) -5 mod -3 = -2
lambert@piring.cwi.nl (Lambert Meertens) (02/27/90)
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