Since its 1983 standard (Forth-83), Forth has implemented floored division as standard. Interestingly, almost all processor architectures natively implement symmetric division.
What is the difference between the two types? In floored division, the quotient is truncated toward minus infinity (remember, this is integer division we’re talking about). In symmetric division, the quotient is truncated toward zero, which means that depending on the sign of the dividend, the quotient can be truncated in different directions. This is the source of its evil.
I’ve thought about this a lot and have come to the conclusion that symmetric division should be considered harmful.
There are two reasons that I think this: symmetric division yields results different from arithmetic right shifts (which floor), and both the quotient and remainder have singularities around zero.
If you’re interested in the (gory) details, read on.
First let’s look at symmetric division. Here is a picture of quotients (Q) and remainders (R) (on Y) plotted against dividends (on X); the divisor is 3.
|
+3 Q
|
+2 Q Q Q
|
+1 Q Q Q
|
-+---+---+---+---+---+---+---Q---Q---Q---Q---Q---+---+---+---+---+---+---+---
-9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
Q Q Q -1
|
Q Q Q -2
|
Q -3
|
|
+2 R R R
|
+1 R R R
|
-R---+---+---R---+---+---R---+---+---R---+---+---R---+---+---R---+---+---R---
-9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
R R R -1
|
R R R -2
|
You can clearly see the “singularities” around zero, both for the quotient and the remainder.
So, why does the remainder change sign? Let’s look at a data sheet. The x86 programmer’s manual says this about IDIV: “Non-integral results are truncated (chopped) towards 0. The sign of the remainder is always the same as the sign of the dividend.”
We see on our graph the sign of the remainder following that of the dividend. But why? Well, if you truncate the quotient toward zero, you have to “take up the slack” in the remainder. Remember, quotient and remainder are defined such that
quot * divisor + rem = dividend.
There are several cases to consider.
If rem == 0, then
quot * divisor = dividend,
and there is no error. This is true regardless of the sign of the quotient. When rem != 0, things become interesting.
If rem != 0, and quotient is >= 0 and truncated toward zero, then
quot * divisor < dividend,
so rem has to be > 0 to compensate.
If rem != 0, and quotient is < 0 and truncated toward zero, then
quot * divisor > dividend,
so rem has to be < 0 to compensate.
So it’s the truncation of the quotient toward zero that forces the sign of the remainder to follow that of the dividend.
Now let’s see the graphs for floored division. Again, dividend on X; quotient Q and modulus M (remainder) on Y. Divisor is 3.
|
+3 Q
|
+2 Q Q Q
|
+1 Q Q Q
|
-+---+---+---+---+---+---+---+---+---Q---Q---Q---+---+---+---+---+---+---+---
-9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
Q Q Q -1
|
Q Q Q -2
|
Q Q Q -3
|
|
M M M +2 M M M
|
M M M +1 M M M
|
-M---+---+---M---+---+---M---+---+---M---+---+---M---+---+---M---+---+---M---
-9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9
-1
|
-2
|
This time there are no singularities! And we see that the sign of the modulus (what the remainder is called when doing floored division) is the same as the sign of the divisor; it does not “cross over” as the dividend becomes negative.
Let’s look at the different cases as we did for symmetric division.
If mod == 0, then
quot * divisor = dividend,
and there is no error. This is true regardless of the sign of the quotient. When mod != 0, things become interesting.
If mod != 0 and quotient >=0 and truncated toward -infinity, then
quot * divisor < dividend,
so mod must be > 0 to compensate.
If mod != 0 and quotient < 0 and truncated toward -infinity, then
quot * divisor < dividend,
so mod must be > 0 to compensate.
These two cases are the same, unlike in the “symmetric” case!
This explains why the “error” that mod represents does not need to change direction when the dividend becomes negative because the direction of truncation (of the quotient) is always “leftward” (towards -infinity).
It’s relatively easy to see from these graphs how to fix symmetric division to make it flooring instead. Where the remainder/modulus is zero, both systems yield the same quotient, so there is nothing to do. Where the quotients differ, they differ by 1: the symmetric quotient is more positive than it should be. Where the remainder and modulus differ they differ by exactly the value of the divisor: the remainder being more negative by that amount.
The differences in quotient and mod/rem between symmetric and floored division are related. We want
symm_quot * divisor + rem = floor_quot * divisor + mod = dividend.
When rem == 0, the quotients are equal, and so mod == 0 as well.
If the quotients differ, then
floor_quot = symm_quot - 1.
This will happen when rem != 0 && sign(divisor) != sign(dividend). In order to compensate, we must have
mod = rem + divisor.
Doing the substitution to check our math:
floor_quot * divisor + mod = (symm_quot - 1) * divisor + (rem + divisor)
= symm_quot * divisor + rem
= dividend.
In conclusion, to fix symmetric division we must calulate
floor_quot = symm_quot - 1
mod = rem + divisor
when rem != 0 && sign(divisor) != sign(dividend).
Here is C code to implement this.
struct qm
{
int quot;
int mod;
};
struct qm div_mod(int dend, int dsor)
{
struct qm res;
res.quot = dend / dsor;
res.mod = dend % dsor;
#ifdef DIVISION_IS_SYMMETRIC
/*
* We now have the results of a stupid symmetric division, which we
* must convert to floored. We only do this if the modulus was non-zero
* and if the dividend and divisor had opposite signs.
*/
if (res.mod != 0 && (dend ^ dsor) < 0)
{
res.quot -= 1;
res.mod += dsor;
}
#endif
return res;
}
Let’s now turn our attention to arithmetic right shift, which Guy Steele, Jr., “considered harmful”. I’d like to turn his argument around and argue that FORTRAN-style (symmetric) division should be “considered harmful”.
If you arithmetic right shift a non-negative number by 1 bit, you get a quotient and a modulus. The quotient is number/2; the mod is 1 or 0. These values correspond exactly to what you would get doing floored or symmetric division.
If you arithmetic right shift a negative number by 1 bit, you get a quotient and a modulus. But in this case you get “funny” answers. Shifting -1 yields -1; shifting -3 yields -2, etc. This is, in some sense, “not what we expect”. Why not?
First, let’s look at the sign of the modulus. The bit shifted out is 1 or 0 – it is non-negative, regardless of the sign of the “dividend”. Since the modulus is taking the sign of the divisor (+2) rather than our negative dividend, we must be doing floored division!
What about multi-bit shifts? Let’s shift by 3 bits. We’ll shift out 3 bits; together they form a non-negative number from 0 to 7. This is our modulus. Again, note that it is non-negative, always! (Note that the easiest way to get the 3 bit modulus is to do copy our initial value and do an AND operation on it, rather than accumulating the bits shifted out.)
By our “compensation” rules above, this forces the shift operation to floor the quotient.
We see now that using ASR and AND as synonyms for DIV and MOD (when our divisor is a power of 2) corresponds exactly if and only if DIV and MOD implement floored division.
But what about “symmetric division considered harmful”? Perhaps a concrete example will illustrate.
Let’s say we’re indexing into an array, and for whatever reason(s), negative indices make sense. We have an array of objects, each 8 bytes long. Someone hands us a byte offset (possibly negative) into our array, and we’d like to convert it to an (array index, offset) pair. (This is a contrived example, but similar mechanics could arise in real code.) What do we do?
Recognizing the power-of-2-ness of 8, we arithmetic right shift. This yields two values: an index (possibly negative), and an offset into the object indexed. (Note that the 3 bits shifted out are a non-negative offset from the beginning of the object.) This will always work, and will always yield useful and correct values, regardless of the sign of the original byte offset.
Now let’s assume our objects are 12 bytes long. Now what do we do? We divide, and our processor’s “native” symmetric division yields useless and erroneous answers. For non-negative indices everything is fine, but for negative indices we get as our two values the index of the item following the one we want (the result of truncating the quotient toward zero) and a negative offset from the following item, back to the byte originally pointed to. Given the argument that symmetric division yields “intuitive” answers, I would have to disagree!
You can imagine that in most kinds of number crunching, graphics, and control applications symmetric division would almost never give you the right answer!
There was a time when I would have agreed with you. But now I think differently.
Symmetric division has a property that you completely forget to mention:
divisor / dividend = (- divisor) / (- dividend)
which is not the case for flored division as you can easily see from the diagrams above. The graph for symmetric division is point symmetric around (0, 0) [I hope “point symmetric” is the right English term for this, it is “punkt-symmetrisch” in German], but the one for floored division is not.
I agree with you that you want a true modulus (which is always positive) for array indexing as in your example. However, in most cases where that is needed, you try to do something like:
a[ (index - x) mod size ] where 0 <= x < size
This can be easily changed to:
a[ (index + size - x) mod size ]
which will give the correct answer even if your division is symmetric. And in most cases x is a constant so that (size – x) can be precalculated.
The real problem are actually the CPU manufacturers and language designers. They use a symmetric division, but include a mod function which would better be called rem for remainder. It would be nice, though, to also have a true mod function that always returns a positive answer.
--Michael Pruemm
I think the real problem is that most people don’t know this distinction even exists (between symmetric and floored division), and most languages (Python and Haskell are exceptions) are ignorant as well. For instance, the C standard(s) basically say: “There are a couple of different answers you might get when you divide; I hope that’s OK”.
I have to disagree with your statement above that
divisor / dividend = (- divisor) / (- dividend)
only for symmetric division. In fact we only floor the quotient (when converting from symmetric to floored) when the divisor and dividend have opposite signs. My graphs only show what happens with a positive divisor when the dividend changes sign, not when both change sign together. In that case, by definition (mine), the symmetric quotient will equal the floored quotient, and the symmetric remainder will equal the floored modulus.