DIV and MOD ( was: Something IBM did right )
Dave Jones
djones at megatest.UUCP
Sat Nov 5 10:02:22 AEST 1988
As is Mr. Switzer, I too am absolutely certain that I know
how / and % should be defined for negative dividends. Peculiar
that we should not agree! :-) We agree on the MOD issue, but
not on DIV. Or maybe not. First he says that IBM "did it right":
> The PC/RT implements / to truncate to smaller values and i%n to always
> return a value (0..n-1) for positive "n"
But then he says,
> Please, do not argue that integer -1/2 should be -1...
But that is, or course, truncation toward a smaller value.
(-1 is smaller than -0.5)
Perhaps he will want to clarify.
I have given the matter quite a bit of thought, ever since
1979, only months after having obtained an M.S. in math,
when I was appalled to discover that the Pascal implementation at
my new place of employment calculated -1 MOD 2 to be a
negative number! Sheesh. I have since become resigned to
the fact that, as the saying goes, "S**t happens."
I am well aware of the fact that writing portable code means
recognizing that most C compilers don't do it the way I would like it.
But I still have strong opinions on the subject, as to what the most
practical definitions of DIV and MOD are. It is no coincidence that
they happen to be the theoretical definitions as well.
I really find it quite astonishing that there is no consesus on
this. It just looks so obvious. There is one way that is beautifully
consistent. All the other ways have hair.
In case you have not figured it out, my vote is along these lines:
-1 % 2 == 1
-1 / 2 == -1
It is not a coincidence that these are the same numbers that you
get from
-1 & 1 == 1
-1 >> 1 == -1
provided that the >> operator does sign extension properly on signed
integers.
The operations of shifting and masking are intimately related
to the arithmetic operations of counting. It has long been
a source of delight and insight for me to take notice of the striking
correspondences between, for example, addition of numbers and disjoint
union of sets -- between masking bits and orthogonal projections in
inner-product spaces -- between the algebra of continued fractions and
the algebra of solving regular expressions -- to name just a few examples.
I propose that if j > 0 then i/j be truncated downward -- by that I
do not mean "toward zero" -- and that i%j is a number in the range
0..(j-1). We will return to the matter of i % (-j) and i/(-j) in a
couple of exercises later on. (I'll give my answers in a spoiler at
the very bottom.)
Okay, now to reality. By what criteria would we choose these
conventions? What are the practical considerations?
In practice, what one wants is to be able to do calculations
that do not require checking the signs of numbers. Also nice is
to use shifts and and negation to optimize code when divisors
and multipliers are positive multiples of two. This can be done by
compilers or by knowledgable/devious programmers (depends on your
point of view), provided that the conventions allow it unambiguously.
You can even extend this to non- powers of two, by using shifts
and adds for multiplication.
But if your definition of DIV or MOD refers to the function ABS, as
does the ANSII Pascal standard, it is pretty likely that checking the
sign (or equivalently, calling ABS) will be required. The ABS
function has a nasty non-linearity at zero. It is equivalent to
say that "changing the sign of the dividend changes sign of the
quotient, but not the magnitude," becuase there is an implicit
"ABS" in the word "magnitude".
Look at the graph of the the functions for DIV2 and MOD3, as I
propose them, and you will see that they breeze through zero
without taking any notice of it, whatsoever.
DIV2
2 X----X
. .
. .
. .
. .
1 X----X
. .
. .
. .
. .
|....|....|....|....X----X....|....|....|....|
-4 -3 -2 -1 0 1 2 3 4 5
. .
. .
. .
X----X -1
. .
. .
. .
. .
X----X -2
Notice that the X's form a neat stairstep with a slope of 1/2.
Everywhere you look at it, it looks exactly the same. There is
nothing peculiar happening about zero. The competing graph has one
"step" that is three units in length: -1, 0, 1. All the other
steps are two units long, just as one would expect of an integral
graph with slope 1/2.
MOD3
X 2 X X
/ . / /
/ . / /
/ . / /
X 1 X X
/ . / /
/ . / /
/ ./ /
X X X
-4..-3..-2..-1..0...1...2...3...4...5
.
.
A nice, regular "ramp function". Again, there is nothing special
about zero. The function looks the same everywhere. The competing
graph "flips over" at zero.
So if we use these definitions, we never have to check the sign
of a dividend.
Notice also that
i == (i/j)*j + i%j
holds for all i, positive and negative alike, when j>0. Same reason.
Nothing out of the ordinary happens at zero.
So how about those nutty negative divisors, eh?
Let's call the property
i == (i/j)*j + i%j
the "Chinese Remainder" property, after the "Chinese Remainder Theorem"
of number theory.
EXERCISE 1. Propose a definitive graph demonstrating the
truncation properties of the function DIV_minus_2.
What alternatives did you consider? Why did you choose the one you did?
How does it extend the principal of truncation?
EXERCISE 2. Can the definition of MOD be extended to include
negative divisors?
If so, propose a definitive graph for MOD_minus_3.
Does it, along with your definition from exercise, 1 have
the Chinese Remainder property?
Spoilers follow.
Answer 1. To obtain a DIV_minus_n graph, flip the DIVn graph
about the X-axis, so that the stairsteps slope down going left-to-right,
rather than up. Sybolicly, define i/(-j) as -(i/j).
Thus truncation of dividends is downward for positive
divisors, and upward for negative divisors. They tend to
"slip down the stairstep" quite consistently.
Answer 2. Define i%(-j) as i%j.
The Chinese Remainder property is preserved by these definitions.
More information about the Comp.lang.c
mailing list