What does % really do?

[Steven T. Hatton]

This is from ISO/IEC 14882:2003(E) §5.6 ¶4
<quote>
The binary / operator yields the quotient, and the binary % operator yields the remainder from the division
of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; oth-
erwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnega-
tive; if not, the sign of the remainder is implementation-defined).
</quote>

How precisely does that actually define the behavior of these operators? I haven't given this last point a
great deal of thought yet, but I believe you could define division of a negative integer by a positive integer
in such a way as to always have a positive remainder. That is, the quotient would be the integer with a magnitude one
greater than the previous whole number division, e.g. -24/5 = -5, with the remainder of 1. That gives
a=-24, b=5, a/b=-5, a%b=1, (a/b)b=-25, (a/b)*b + a%b=-24.

Here's something interesting to consider. I started looking at the way C++ handles the % operator, and found that the
the behavior of my compiler is different from that of Mathematica in this respect. I also looked at K&R where I saw
that they were rather explicit about not defining which choice from the above options could be used. Look at the
output of the C++ program compared with the Mathematica version of (almost) the same program. I will note that the
C++ Standard does not call the % operation 'modulo', at least not in the above quoted paragraph. The is, however, often
called that. I contend that the behavior of my C++ compiler does _not_ provide a true modulo operation. A true molulo
operator would produce only one modulus per equivalence set. The program below does not do that.

#include <iostream>
#include <vector>
#include <map>
#include <iomanip>

typedef std::vector<int> intVector;
typedef std::map<int,intVector> equivalenceSets;

void printEquivelenceSets(equivalenceSets& es, int n) {

for(equivalenceSets::iterator it = es.begin(); it != es.end(); ++it ) {

std::cout<<"modulus = "<<std::setw(2)<<it->first<<" "<<"{";

for(unsigned j = 0; j < it->second.size(); ++j) {
if(j) std::cout << ", ";
std::cout<<std::setw(4)<< it->second[j];
}
std::cout<<"}"<<std::endl;
}

std::cout<<std::endl;
for(equivalenceSets::iterator it = es.begin(); it != es.end(); ++it ) {

std::cout<<"modulus = "<<it->first<<" "<<"{";

for(unsigned j = 0; j < it->second.size(); ++j) {
if(j) std::cout << ",";
if(!(it->first || it->second[j])) std::cout << std::endl;

std::cout<<"("<<it->second[j]<<"-";

if(it->first < 0) std::cout<<"("<<it->first<<")";
else std::cout<<it->first;

std::cout<<")/"<<"("<<n<<")="<<float(it->second[j] - it->first)/float(n);
}
std::cout<<"}"<<std::endl;
}
}

int main() {
int a(0);
int b(0);
int n(5);

equivalenceSets es;

for (int a = -25; a < 26; ++a ) {
es[a%n].push_back(a);
}

printEquivelenceSets(es, n);
}


modulus = -4 { -24, -19, -14, -9, -4}
modulus = -3 { -23, -18, -13, -8, -3}
modulus = -2 { -22, -17, -12, -7, -2}
modulus = -1 { -21, -16, -11, -6, -1}
modulus = 0 { -25, -20, -15, -10, -5, 0, 5, 10, 15, 20, 25}
modulus = 1 { 1, 6, 11, 16, 21}
modulus = 2 { 2, 7, 12, 17, 22}
modulus = 3 { 3, 8, 13, 18, 23}
modulus = 4 { 4, 9, 14, 19, 24}

modulus = -4 {(-24-(-4))/(5)=-4,(-19-(-4))/(5)=-3,(-14-(-4))/(5)=-2,(-9-(-4))/(5)=-1,(-4-(-4))/(5)=0}
modulus = -3 {(-23-(-3))/(5)=-4,(-18-(-3))/(5)=-3,(-13-(-3))/(5)=-2,(-8-(-3))/(5)=-1,(-3-(-3))/(5)=0}
modulus = -2 {(-22-(-2))/(5)=-4,(-17-(-2))/(5)=-3,(-12-(-2))/(5)=-2,(-7-(-2))/(5)=-1,(-2-(-2))/(5)=0}
modulus = -1 {(-21-(-1))/(5)=-4,(-16-(-1))/(5)=-3,(-11-(-1))/(5)=-2,(-6-(-1))/(5)=-1,(-1-(-1))/(5)=0}
modulus = 0 {(-25-0)/(5)=-5,(-20-0)/(5)=-4,(-15-0)/(5)=-3,(-10-0)/(5)=-2,(-5-0)/(5)=-1,
(0-0)/(5)=0,(5-0)/(5)=1,(10-0)/(5)=2,(15-0)/(5)=3,(20-0)/(5)=4,(25-0)/(5)=5}
modulus = 1 {(1-1)/(5)=0,(6-1)/(5)=1,(11-1)/(5)=2,(16-1)/(5)=3,(21-1)/(5)=4}
modulus = 2 {(2-2)/(5)=0,(7-2)/(5)=1,(12-2)/(5)=2,(17-2)/(5)=3,(22-2)/(5)=4}
modulus = 3 {(3-3)/(5)=0,(8-3)/(5)=1,(13-3)/(5)=2,(18-3)/(5)=3,(23-3)/(5)=4}
modulus = 4 {(4-4)/(5)=0,(9-4)/(5)=1,(14-4)/(5)=2,(19-4)/(5)=3,(24-4)/(5)=4}


(*Mathematica version of the same program*)

getIndex[r_Integer, eqsl_List] := 0 /; eqsl === {} || Position[eqsl, {r, ___}] === {}
getIndex[r_Integer, eqsl_List] := Position[eqsl, {r, ___}][[1, 1]]

addToEqSetList[r_Integer, n_Integer, eqsl_List] := {{Mod[r, n], r}} /; eqsl === {}

addToEqSetList[r_Integer, n_Integer, eqsl_List] :=
Module[{i = getIndex[Mod[r, n], eqsl]},
ReplacePart[eqsl, Append[eqsl[[ i ]], r], i] /; i > 0]

addToEqSetList[r_Integer, n_Integer, eqsl_List] := Append[eqsl, {Mod[r, n], r}]

eqSetList = {};
n = 5;
r = 25;
Do[eqSetList = addToEqSetList[i, n, eqSetList], {i, -r, r}]

eqSetList // TableForm

0 -25 -20 -15 -10 -5 0 5 10 15 20 25

1 -24 -19 -14 -9 -4 1 6 11 16 21

2 -23 -18 -13 -8 -3 2 7 12 17 22

3 -22 -17 -12 -7 -2 3 8 13 18 23

4 -21 -16 -11 -6 -1 4 9 14 19 24

 

[Steven T. Hatton]

Steven T. Hatton wrote:

Replace equivalence set, with equivalence class. I'm tired.

 

[Ivan Vecerina]

This is from ISO/IEC 14882:2003(E) §5.6 ¶4
<quote>
The binary / operator yields the quotient, and the binary % operator
yields the remainder from the division
of the first expression by the second. If the second operand of / or % is
zero the behavior is undefined; oth-
erwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then
the remainder is nonnega-
tive; if not, the sign of the remainder is implementation-defined).
</quote>

How precisely does that actually define the behavior of these operators? I
haven't given this last point a
great deal of thought yet, but I believe you could define division of a
negative integer by a positive integer
in such a way as to always have a positive remainder.

Yes. It just happens that on some processor architectures,
the 'modulo' operation with negative operands does not always
provide a positive result. In the same fashion, (-3)/2 may
yield -1 or -2, depending on the processor.

And to avoid forcing implementations to add special handling
for this 'unusual' case of non-positive integer division, it
had been decided to leave this choice up to the implementation.

Obviously, Mathematica, Java, C#, and other language/platform
specifications have made a different choice. And nowadays,
this freedom of implementation seems archaic (and some have
suggested to remove it), but that's the way C and C++ are...


hth -Ivan

 

[Pete Becker]

Obviously, Mathematica, Java, C#, and other language/platform
specifications have made a different choice. And nowadays,
this freedom of implementation seems archaic (and some have
suggested to remove it), but that's the way C and C++ are...

They're that way because it's fast. If you want slow and always positive
you can write it. If the language requires slow and always positive you
can't make it fast.

 

[Ivan Vecerina]

They're that way because it's fast. If you want slow and always positive
you can write it. If the language requires slow and always positive you
can't make it fast.

Well, you could have it be fast with unsigned operands anyway.
And for signed operands, how useful is an unpredictable result?

This said, things are the way they are, and I'm fine with it.
And I'm not up for a debate which must have been hashed out already...

Regards,
Ivan

 

[Pete Becker]

Well, you could have it be fast with unsigned operands anyway.

It _is_ fast for unsigned operands.

And for signed operands, how useful is an unpredictable result?

It's not unpredictable. It's implementation-defined, within the
constraints imposed by its definition, which means it is one of two
possible values. If you want a non-negative remainder, just check it. If
it's negative, add the absolute value of the denominator.

This said, things are the way they are, and I'm fine with it.
And I'm not up for a debate which must have been hashed out already...

Then don't make provocative (and erroneous) statements.

 

[Ivan Vecerina]

It _is_ fast for unsigned operands.

Yes, my point was that it *could* still be fast for unsigned operands,
had the specification strictly defined the result of a signed operation.

It's not unpredictable. It's implementation-defined, within the
constraints imposed by its definition, which means it is one of two
possible values. If you want a non-negative remainder, just check it. If
it's negative, add the absolute value of the denominator.

I obviously understand this. Why are you nitpicking on wording?
From the perspective of a C++ programmer writing portable code,
it is not strictly predictable - since a run-time test and
fix is likely to be required.

Now since you are keeping this discussion going:
Could you provide us with real-life examples were the remainder of
a signed division is needed, but the sign of the result is indifferent?

I could not think of such a case.
But I guess the point is to support fast division with signed operands,
and I understand that the rounding in this case may have to be
implementation-defined, for performance reasons. And it is obviously
essential to keep the results of % and / consistent.

Other standards committees have chosen a different approach. As I said,
I'm fine with either choice - you don't need to preach and convert me.
I just tried to explain the situation to the OP, and I did my best
to expose it in a neutral light. ( forgive me, I'm Swiss )

Then don't make provocative (and erroneous) statements.

The provocativeness of my previous 4-line post has totally escaped me
- I would be thankful if you could explain what was so sensitive in it.
I do not see either how my comment was fundamentally erroneous - in
what way could it have misled or otherwise harmed the OP ?


Kind regards,
Ivan

 

[Pete Becker]

Yes, my point was that it *could* still be fast for unsigned operands,
had the specification strictly defined the result of a signed operation.

Oh, so your point was that making signed divisions slow would be okay
because it wouldn't affect unsigned divisions. Okay, true, but not
particularly relevant. The basic principle of C and C++ is that you
don't pay for what you don't use.

I obviously understand this. Why are you nitpicking on wording?
From the perspective of a C++ programmer writing portable code,
it is not strictly predictable - since a run-time test and
fix is likely to be required.

"Unpredictable" is not a word I would use to describe something that's
perfectly well defined, clear, and easily manageable.

 

[Andrew Koenig]

I could not think of such a case.
But I guess the point is to support fast division with signed operands,
and I understand that the rounding in this case may have to be
implementation-defined, for performance reasons. And it is obviously
essential to keep the results of % and / consistent.

The real issue is much simpler: The C++ committee decided early in the game
to maintain compatibility with C in fundamental areas such as arithmetic.
C89, on which C++ is based, defines % and / so as to allow the
implementation's hardware arithmetic to show through, so C++does the same.

I believe that C99 requires that the result of % have the same sign as the
dividend. If my belief is correct, I am confident that C++ will follow suit
in its next revision.